Binary Trees & BSTs

Binary Trees & BSTs | Algoryva

Implementation

Building a tree in Python

A node stores a value and two links, each either another node or None. The insert function below builds a binary search tree: smaller values go left, others go right.

python

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def insert(root, v):
    if root is None:
        return Node(v)
    if v < root.val:
        root.left = insert(root.left, v)
    else:
        root.right = insert(root.right, v)
    return root

root = None
for v in [8, 4, 12, 2, 6, 10, 14]:
    root = insert(root, v)

print(root.val, root.left.val, root.right.val)   # 8 4 12
print(root.left.left.val, root.left.right.val)   # 2 6

Reading the code

›Node.__init__ stores the value and defaults both children to None, meaning “no child”.
›insert is recursive: an empty spot (None) becomes a new node; otherwise we descend left or right and re-attach the returned subtree. Re-attaching looks redundant but is what makes the new node hang off its parent.
›Inserting 8, 4, 12, 2, 6, 10, 14 produces a perfectly balanced tree with 8 at the top, 4 and 12 below it, and four leaves.
›The shape depends on insertion order; we will see why that matters in the complexity section.

Worked by hand

The four orders side by side

All four visit the same seven nodes of the tree in the animations (root 8; children 4 and 12; leaves 2, 6, 10, 14). Only the moment of the visit changes.

traversal	rule	sequence
preorder	node, left, right	8 4 2 6 12 10 14
inorder	left, node, right	2 4 6 8 10 12 14
postorder	left, right, node	2 6 4 10 14 12 8
level order	row by row	8 \| 4 12 \| 2 6 10 14

1
Preorder is a “copy” order
Parents come before children, so rebuilding a tree by inserting in preorder recreates its exact shape. It is also how you would print a folder tree.
2
Inorder gives sorted output for a BST
Everything smaller than a node is in its left subtree and is visited first.
3
Postorder is a “clean-up” order
Children before parents: delete or size-up the subtree before its root.

Implementation

The four traversals in code

The three depth-first orders differ only in *where* the current node is added to the answer.

Plan in plain steps

pseudocode

preorder(n):  if n is None: return nothing; record n; preorder(left); preorder(right)
inorder(n):   inorder(left); record n; inorder(right)
postorder(n): postorder(left); postorder(right); record n
level order:  queue with the root; repeatedly dequeue a node, record it, enqueue its children

python

from collections import deque

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def insert(root, v):
    if root is None:
        return Node(v)
    if v < root.val:
        root.left = insert(root.left, v)
    else:
        root.right = insert(root.right, v)
    return root

root = None
for v in [8, 4, 12, 2, 6, 10, 14]:
    root = insert(root, v)

def preorder(n):
    return [] if n is None else [n.val] + preorder(n.left) + preorder(n.right)

def inorder(n):
    return [] if n is None else inorder(n.left) + [n.val] + inorder(n.right)

def postorder(n):
    return [] if n is None else postorder(n.left) + postorder(n.right) + [n.val]

 (root):
    out, q = [], ([root]  root  [])
     q:
        row = []
         _  ((q)):          
            n = q.()
            row.(n.val)
             n.left:
                q.(n.left)
             n.right:
                q.(n.right)
        out.(row)
     out

((root))   
((root))   
((root))   
((root))

Reading the code

›The base case n is None returns an empty list, so a missing child contributes nothing.
›Moving [n.val] between the two recursive calls is the *only* difference between the three orders.
›In level_order, for _ in range(len(q)) captures the queue length at the start of the row, so exactly the nodes of one level are processed before the next row begins.
›Concatenating lists is simple but copies; for large trees append to one shared list instead.

Implementation

The core pattern: ask the children, then combine

Height, size, and sum all have the same shape. Write them once and you can write any of them.

python

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def insert(root, v):
    if root is None:
        return Node(v)
    if v < root.val:
        root.left = insert(root.left, v)
    else:
        root.right = insert(root.right, v)
    return root

root = None
for v in [8, 4, 12, 2, 6, 10, 14]:
    root = insert(root, v)

def height(n):
    if n is None:
        return 0
    return 1 + max(height(n.left), height(n.right))

def size(n):
    if n is None:
        return 0
    return 1 + size(n.left) + size(n.right)

def leaves(n):
    if n is None:
        return 0
    if n.left is None and n.right is None:
        return 1
    return leaves(n.left) + leaves(n.right)

print(height(root))   # 3
print(size(root))   # 7
print(leaves(root))   # 4

Reading the code

›height(None) = 0 is the base. A node adds 1 to the taller of its two subtrees.
›size adds both subtrees plus the node itself.
›leaves needs a second base case: a node with no children *is* a leaf and returns 1, otherwise it would count 0 forever.
›Each function visits every node once, so each is O(n).

Worked problem

Is this a valid binary search tree?

The problem

Given the root of a binary tree, return True if it is a valid BST: every node's left subtree holds only smaller values and its right subtree only larger values.

Checking only each node against its direct children is not enough. Take root 5 with a right child 6, and give 6 a left child 3. Locally 3 < 6 looks fine, yet 3 sits in the right subtree of 5, where every value must be larger than 5.
So pass down a range (lo, hi) that every value in the subtree must lie inside.
Going left tightens the upper bound to the current value; going right raises the lower bound.
If any node falls outside its range, the tree is invalid.

python

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def is_bst(n, lo=float("-inf"), hi=float("inf")):
    if n is None:
        return True
    if not (lo < n.val < hi):
        return False
    return is_bst(n.left, lo, n.val) and is_bst(n.right, n.val, hi)

good = Node(2, Node(1), Node(3))
bad = Node(5, Node(1), Node(6, Node(3), Node(7)))
print(is_bst(good))   # True
print(is_bst(bad))   # False

Takeaway. Information can flow *down* the tree as parameters (the allowed range) as well as *up* through return values. In bad, node 3 is correctly smaller than its parent 6, so a parent-only check passes it. But the range handed down from the root says right-subtree values must be greater than 5, and 3 is not.

Worked problem

Lowest common ancestor in a BST

The problem

In a binary search tree, find the lowest node that has both p and q in its subtree (a node counts as its own descendant).

Start at the root.
If both values are smaller than the current node, the answer lies in the left subtree; if both are larger, in the right subtree.
Otherwise the two values are on different sides (or one equals the current node): the current node is the split point, and therefore the answer.
Each step discards a subtree, so it is O(h), with no recursion needed.

python

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def insert(root, v):
    if root is None:
        return Node(v)
    if v < root.val:
        root.left = insert(root.left, v)
    else:
        root.right = insert(root.right, v)
    return root

root = None
for v in [8, 4, 12, 2, 6, 10, 14]:
    root = insert(root, v)

def lca(root, p, q):
    n = root
    while n:
        if p < n.val and q < n.val:
            n = n.left
        elif p > n.val and q > n.val:
            n = n.right
        else:
            return n.val
    return None

print(lca(root, 2, 6))   # 4
print(lca(root, 2, 14))   # 8
print(lca(root, 4, 6))   # 4

Takeaway. The BST property lets one comparison discard an entire subtree, the same halving idea as binary search, applied to a tree. On a general (unordered) tree you would have to search both sides.

Wrap-up

Remember this

A tree is a node plus smaller trees, so most tree algorithms are short recursive functions with a None base case.
Preorder, inorder and postorder differ only in when the node is visited; level order uses a queue.
Inorder traversal of a BST is sorted, and the BST rule lets one comparison discard a whole subtree.
Information can flow down (bounds) or up (return values); choose by what each node needs.
Cost is O(n) for traversals and O(h) for BST operations, where the height depends on the shape.

Cheat sheet

Tree is: empty, or a node + left tree + right tree
Pattern: if n is None: base; ask left; ask right; combine
Preorder / inorder / postorder: node before / between / after its children
Level order: queue (BFS), one row at a time
BST rule: left < node < right, for the whole subtree; inorder is sorted
Cost: traversals O(n); BST search O(h): log n balanced, n degenerate

Top traps to avoid

Forgetting the None base case, so the code crashes on None.left.
Validating a BST by comparing each node only with its direct children.
Mixing up the three depth-first orders.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.For the lesson's tree (root 8; children 4, 12; leaves 2, 6, 10, 14), what is the inorder sequence?
2.Which traversal is the right choice when a node's answer depends on its children's answers (such as the size of a folder)?
3.What is the time of searching a BST with n nodes that was built by inserting 1, 2, 3, …, n in increasing order?
4.“Print the nodes at each depth separately” suggests:
5.Why is checking only a node's direct children not enough to validate a BST?
6.height from the lesson returns 3 for the sample tree. What would height(None) return?
7.Insert 5, 3, 8, 1 into a binary search tree, then print its in-order traversal.
8.Tree: root 1, left child 2 (with left child 4), right child 3. What is its height, counting nodes on the longest root-to-leaf path?
9.In the BST built from 5, 3, 8, 1, does a search for 4 find it?
10.Which traversal of a binary search tree visits the keys in sorted order?
11.Search in a balanced BST of n nodes: what is the time?
12.Search in a BST built from already-sorted keys (a chain) of n nodes: what is the time?
13.What does the binary-search-tree property require?
14.Level-order (breadth-first) traversal of root 1 with left 2 (left 4) and right 3. What is printed?
15.Why can an unbalanced BST perform badly?

Binary Trees & BSTs

After this lesson you will be able to

Builds on

Unlocks

Folders inside folders

Vocabulary

A tree is a node plus two smaller trees

Building a tree in Python

Reading the code

Preorder: visit the node first

Inorder: visit the node between its children

Postorder: visit the node last

Level order: row by row

The four orders side by side

The four traversals in code

Reading the code

The core pattern: ask the children, then combine

Reading the code

Why O(n) and why shape matters

Edge cases

Mistakes to avoid

How to spot a tree problem

Is this a valid binary search tree?

Lowest common ancestor in a BST

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up3 problems

Core9 problems

Application31 problems

Challenge17 problems