Unit 12 — Binary Trees & Traversals

A school record system may need to search for one student, or score every record, without scanning unrelated branches. A binary tree gives each record at most two child positions, so one recursive walking pattern can search or score the whole structure fast. We store the tree as PARALLEL ARRAYS (no classes) and build it as a short ladder of executable demos with a Notice, then a full stdin solver.

You will learn

Store a binary tree without a class, using val, left and right lists with -1 for no child.
Walk a whole tree recursively in pre-order, stopping at empty children.
Compute values such as the height of a tree by recursion.
Search a binary search tree, find where a new key goes and check that a tree is a valid BST.

Lesson 1 — Store a Binary Tree Without Classes

Number the nodes 0..n-1. val[i], left[i], right[i] hold node i's value and its two child INDICES; a child of -1 means "none". Always check == -1 BEFORE indexing (arr[-1] would silently read the last node).

val = [8, 3, 10]
left = [1, -1, -1]
right = [2, -1, -1]
root = 0
print("root value:", val[root])
if left[root] == -1:
    print("no left child")
else:
    print("left child value:", val[left[root]])

Output

root value: 8
left child value: 3

Notice

Node 0 is the root (value 8); left[0] == 1 points to the child at index 1. The -1 sentinel is checked before any val[...] lookup.

A recursive PRE-order walk visits a node, then its left subtree, then its right — base case node == -1 returns the empty string.

val = [8, 3, 10]
left = [1, -1, -1]
right = [2, -1, -1]

def preorder(node):
    if node == -1:
        return ""
    text = str(val[node])
    left_text = preorder(left[node])
    right_text = preorder(right[node])
    if left_text != "":
        text = text + " " + left_text
    if right_text != "":
        text = text + " " + right_text
    return text

print(preorder(0))

Output

8 3 10

Notice

preorder(0) → 8 3 10; the recursion stops at each -1 child. This is the walking pattern the solver ships.

A traversal can RETURN a number up the tree instead of a string — here the height, base case 0.

val = [8, 3, 10]
left = [1, -1, -1]
right = [2, -1, -1]

def height(node):
    if node == -1:
        return 0
    return 1 + max(height(left[node]), height(right[node]))

print(height(0))

Output

Notice

height returns 1 + max(left, right); empty subtrees return 0, so this 3-node tree has height 2.

Put it together: the program reads n, the root index, then n value left right triples, and prints the pre-order values.

Try it yourself

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
root = int(tokens[1])
val = []
left = []
right = []
position = 2
i = 0
while i < n:
    val.append(int(tokens[position]))
    left.append(int(tokens[position + 1]))
    right.append(int(tokens[position + 2]))
    position = position + 3
    i = i + 1

def preorder(node):
    if node == -1:
        return ""
    text = str(val[node])
    left_text = preorder(left[node])
    right_text = preorder(right[node])
    if left_text != "":
        text = text + " " + left_text
    if right_text != "":
        text = text + " " + right_text
    return text

print(preorder(root))

Run the full solver from this unit folder:

python assets/l1.py < assets/l1/1.in

Notice

A nested preorder recurses left then right, joining values with spaces; -1 children stop the recursion.

Complexity: O(n) — each node is visited once.

Lesson 2 — Binary Search Trees

A binary search tree keeps left subtree < node < right subtree, so a search goes ONE way at each node instead of scanning everything.

val = [8, 3, 10, 1, 6]
left = [1, 3, -1, -1, -1]
right = [2, 4, -1, -1, -1]
target = 6
node = 0
found = False
while node != -1 and found == False:
    if val[node] == target:
        found = True
    elif target < val[node]:
        node = left[node]
    else:
        node = right[node]
print(found)

Output

True

Notice

Searching for 6: 6 < 8 → go left to 3; 6 > 3 → go right to 6 — found, without touching the 10 subtree. (An iterative walk here; the solver recurses.)

INSERTION follows the same comparisons until it reaches an empty (-1) slot — that is where the new key belongs.

val = []
left = []
right = []

def insert(node, key):
    if node == -1:
        val.append(key)
        left.append(-1)
        right.append(-1)
        return len(val) - 1
    if key < val[node]:
        left[node] = insert(left[node], key)
    else:
        right[node] = insert(right[node], key)
    return node

root = -1
for key in [8, 3, 10, 1, 6]:
    root = insert(root, key)
print("root index:", root, "values:", val)

Output

root index: 0 values: [8, 3, 10, 1, 6]

Notice

Key 6 walks 8 → 3 and then the right child of 3 is -1, so 6 would attach there.

VALIDATE a BST by passing down a (low, high) bound each node must fall strictly inside — checking a node against only its parent is not enough.

val = [8, 3, 10]
left = [1, -1, -1]
right = [2, -1, -1]

def valid(node, low, high):
    if node == -1:
        return True
    if val[node] <= low or val[node] >= high:
        return False
    return valid(left[node], low, val[node]) and valid(right[node], val[node], high)

print(valid(0, -1000, 1000))

Output

True

Notice

valid narrows the bound going down (low..val left, val..high right); every node stays inside its window, so this tree is valid.

Put it together: the program reads n, root, a target, then the n triples, and prints YES if the target is in the BST, else NO.

Try it yourself

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
root = int(tokens[1])
target = int(tokens[2])
val = []
left = []
right = []
position = 3
i = 0
while i < n:
    val.append(int(tokens[position]))
    left.append(int(tokens[position + 1]))
    right.append(int(tokens[position + 2]))
    position = position + 3
    i = i + 1

def contains(node):
    if node == -1:
        return False
    if val[node] == target:
        return True
    if target < val[node]:
        return contains(left[node])
    return contains(right[node])

if contains(root):
    print("YES")
else:
    print("NO")

Run the full solver from this unit folder:

python assets/l2.py < assets/l2/1.in

Notice

A nested contains compares the target to each node and recurses LEFT or RIGHT; a -1 child ends the search with NO.

Complexity: O(h) — h is the tree height.

Binary Tree Checklist

(1) Identify the root and what each child index means; (2) -1 = no child — check it before indexing; (3) pick the traversal (pre/in/post) the problem needs; (4) for a BST, compare and go ONE way; (5) recursion base case is node == -1.

Recap

Node i has value val[i] and children left[i] and right[i]; check == -1 before indexing.
Pre-order visits a node, then its left subtree, then its right subtree; node == -1 is the base case.
height returns 1 + max(left height, right height), and an empty subtree gives 0.
In a BST, left subtree < node < right subtree, so a search or an insert goes ONE way at each node.
Validate a BST by passing down a (low, high) window that every node must fall inside.

You can now store, walk and search binary trees with recursion.