Trees and Binary Search Trees

Why trees matter

In Linked Lists, you learned that nodes can point to other nodes. A linked list is a chain: each node usually points to one next node.

A tree keeps the node idea, but lets one node point to multiple children. That gives us a shape for hierarchical data:

• folders inside folders
• comments and replies
• company org charts
• parsed math expressions
• decision paths in interview problems

For interview prep, trees are important because they combine pointers, ordering, and search shortcuts. Binary Search Trees, or BSTs, are the first tree structure where shape creates speed.

The basic tree words

A tree is made of nodes connected by parent-to-child links.

        A        <- root
      /   \
     B     C     <- children of A
    / \
   D   E         <- leaves

Key terms:

• Root: the top node. Here, A.
• Parent: a node directly above another node. B is parent of D and E.
• Child: a node directly below another node.
• Leaf: a node with no children. C, D, and E are leaves.
• Subtree: any node plus everything below it.
• Height: how many levels/edges you may need to go down.

A binary tree is a tree where each node has at most two children, often called left and right.

Given this tree:

        A
      /   \
     B     C
    / \
   D   E

Which option lists only leaf nodes?

Binary Search Tree rule

A Binary Search Tree is a binary tree with an ordering rule:

For every node:

• values in the left subtree are smaller
• values in the right subtree are larger

Example:

        50
      /    \
    30      70
   /  \    /  \
 20   40  60   80

This is not just about the direct children. The entire left subtree of 50 must be less than 50, and the entire right subtree must be greater than 50.

That global rule is what lets us search efficiently.

Searching a BST

Searching a BST feels like binary search from Sorting and Searching, but on nodes instead of array indexes.

At each node:

• if target equals node value, found it
• if target is smaller, go left
• if target is larger, go right

You do not scan every node unless the tree shape is bad. You follow one path downward.

```python
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def insert(root, value):
    if root is None:
        return Node(value)

    current = root
    while True:
        if value < current.value:
            if current.left is None:
                current.left = Node(value)
                break
            current = current.left
        else:
            if current.right is None:
                current.right = Node(value)
                break
            current = current.right
    return root


def contains(root, target):
    current = root
    while current is not None:
        if target == current.value:
            return True
        elif target < current.value:
            current = current.left
        else:
            current = current.right
    return False


root = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, value)

for target in [40, 65, 80]:
    print(target, contains(root, target))
```

True or false:

Searching in a Binary Search Tree is always O(log n), no matter what order values were inserted.

Visiting every node

Sometimes you do not want to search for one value. You want to visit every node.

Common traversal orders:

• Preorder: node, left, right
• Inorder: left, node, right
• Postorder: left, right, node

For a BST, inorder traversal returns values in sorted order. That is a favorite interview observation.

We will use small recursive helpers here. Later, the Recursion and Backtracking lesson will make this pattern feel more systematic.

```python
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)


def preorder(node):
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)


def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)


def postorder(node):
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.value]


print('preorder:', preorder(root))
print('inorder:', inorder(root))
print('postorder:', postorder(root))
```

For a Binary Search Tree, an ____ traversal visits values in sorted ascending order.

The important complexity idea

From Time and Space Complexity Analysis, you already know we care about how work grows.

For BST search, insert, and delete, the key variable is usually tree height, often written as h.

• Balanced tree: h ≈ log n, so search is O(log n)
• Skewed tree: h ≈ n, so search is O(n)

Balanced shape:

        4
      /   \
     2     6
    / \   / \
   1  3  5  7

Skewed shape:

1
 \
  2
   \
    3
     \
      4

Interview takeaway: a BST gives fast search only when its height stays small.

Common interview task

A classic BST question is: is this binary tree actually a valid BST?

The subtle part: checking only each node against its immediate children is not enough.

Each node must obey a range created by all ancestors:

• go left: update the upper bound
• go right: update the lower bound

This pattern is useful in coding interviews because it tests whether you understand the global BST rule, not just the local shape.

```python
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def is_valid_bst(node, low=float('-inf'), high=float('inf')):
    if node is None:
        return True

    if not (low < node.value < high):
        return False

    return (
        is_valid_bst(node.left, low, node.value)
        and is_valid_bst(node.right, node.value, high)
    )


valid = Node(10)
valid.left = Node(5)
valid.right = Node(15)
valid.right.left = Node(12)
valid.right.right = Node(20)

invalid = Node(10)
invalid.left = Node(5)
invalid.right = Node(15)
invalid.right.left = Node(6)   # This is less than 10, so it breaks the global rule.
invalid.right.right = Node(20)

print('valid tree:', is_valid_bst(valid))
print('invalid tree:', is_valid_bst(invalid))
```

When validating whether a binary tree is a valid Binary Search Tree, which idea is most important?