\

Chapter 9: Binary Trees

6 min read

Chapter 9 Overview: Binary Trees

Binary trees are fundamental hierarchical data structures. Each node has at most two children, referred to as the left child and the right child. They are essential for representing data with a branching structure, such as file systems, expression evaluation, and search trees.

Key Binary Tree Concepts:

  • Node: The basic unit of a tree, containing data and pointers to its children.
  • Root: The topmost node in a tree.
  • Leaf: A node with no children.
  • Depth: The length of the path from the root to a node. The root’s depth is 0.
  • Height: The length of the longest path from a node to a leaf. The height of a leaf is 0. The height of a tree is the height of its root.
  • Full Binary Tree: A tree where every node has either 0 or 2 children.
  • Complete Binary Tree: A tree where all levels are completely filled except possibly the last, and the last level has all keys as left as possible.
  • Perfect Binary Tree: A tree where all interior nodes have two children and all leaves are at the same level.

Tree Traversal:

The three primary ways to visit all nodes in a tree are:

  1. In-order Traversal: Left subtree -> Visit Root -> Right subtree. For a Binary Search Tree (BST), this yields the nodes in sorted order.
  2. Pre-order Traversal: Visit Root -> Left subtree -> Right subtree. Often used to create a copy of the tree.
  3. Post-order Traversal: Left subtree -> Right subtree -> Visit Root. Often used to delete nodes from the tree.

Section 9.1: Test if a Binary Tree is Height-Balanced

The Problem: A binary tree is height-balanced if, for every node, the difference in height between its left and right subtrees is at most 1. Write a function to determine if a given binary tree is height-balanced.

Algorithm (Recursive Post-order Traversal): A brute-force approach would be to compute the height of the left and right subtrees for every node, which is inefficient (O(n^2)). A better approach integrates the height calculation with the balance check.

  1. Create a recursive helper function, say check_balance(node). This function will return two pieces of information: whether the subtree at node is balanced, and what its height is. A common way to do this is to return a special value (like -1) to signal imbalance.

  2. check_balance(node) logic:

    • Base Case: If node is None, it’s a balanced subtree of height -1 (or 0, depending on convention). Return (True, -1).
    • Recursive Step:
      • Recursively call check_balance on the left child. Get is_left_balanced and left_height.
      • If is_left_balanced is False, this subtree is not balanced. Propagate the failure up: return (False, 0).
      • Recursively call check_balance on the right child. Get is_right_balanced and right_height.
      • If is_right_balanced is False, propagate the failure up: return (False, 0).
    • Check Current Node:
      • Check if the current node is balanced: abs(left_height - right_height) <= 1.
      • If it is, the height of the current node’s subtree is 1 + max(left_height, right_height). Return (True, height).
      • If it’s not, return (False, 0).

Complexity:

  • Time: O(n), as each node is visited once.
  • Space: O(h), where h is the height of the tree, for the recursion stack. O(log n) for a balanced tree, O(n) for a skewed tree.

Section 9.2: Test if a Binary Tree is a Binary Search Tree (BST)

The Problem: Write a function to check if a given binary tree is a valid Binary Search Tree (BST).

BST Property: For any given node N:

  1. All values in N’s left subtree must be less than N’s value.
  2. All values in N’s right subtree must be greater than N’s value.
  3. Both the left and right subtrees must also be binary search trees.

Pitfall: A common mistake is to only check if node.left.data < node.data and node.right.data > node.data. This is not sufficient. The property must hold for all nodes in the subtree, not just the immediate children.

Algorithm (Recursive with Min/Max Range): The most robust method is to perform a recursive traversal, passing down the valid range of values (min_val, max_val) that a node’s value is allowed to have.

  1. Create a recursive helper function is_bst_helper(node, min_val, max_val).

  2. is_bst_helper logic:

    • Base Case: If node is None, it’s a valid BST. Return True.
    • Check Current Node:
      • If node.data <= min_val or node.data >= max_val, the BST property is violated. Return False.
    • Recursive Step:
      • Recursively check the left subtree. The new max_val for the left subtree is the current node’s value: is_bst_helper(node.left, min_val, node.data).
      • Recursively check the right subtree. The new min_val for the right subtree is the current node’s value: is_bst_helper(node.right, node.data, max_val).
      • The tree is a BST if both recursive calls return True.

  3. Initial call: is_bst_helper(root, -infinity, +infinity).

Section 9.4: Find the Lowest Common Ancestor (LCA) in a BST

The Problem: Given a BST and two nodes s and b (smaller and bigger value), find their Lowest Common Ancestor (LCA). The LCA is the deepest node in the tree that has both s and b as descendants.

Algorithm (Exploiting BST Properties): The search for the LCA in a BST is much simpler than in a generic binary tree. We can use the BST property to guide our search from the root.

  1. Start with current = root.
  2. Loop as long as current is not None:
    • If current.data is greater than both s.data and b.data, it means both nodes are in the left subtree. The LCA must also be in the left subtree. So, move left: current = current.left.
    • If current.data is less than both s.data and b.data, it means both nodes are in the right subtree. The LCA must also be in the right subtree. So, move right: current = current.right.
    • Otherwise, current.data is between s.data and b.data (or equal to one of them). This means the path to s and b diverges at current. Therefore, current is the LCA. Return current.

Complexity:

  • Time: O(h), where h is the height of the tree. In the worst case (a skewed tree), this is O(n). For a balanced tree, it’s O(log n).
  • Space: O(1) for the iterative approach.

Section 9.7: Implement an In-order Traversal without Recursion

The Problem: Perform an in-order traversal of a binary tree without using recursion, which implicitly uses the call stack. You must use an explicit stack data structure.

Algorithm (Iterative with a Stack): This approach mimics what the recursion call stack does.

  1. Initialize an empty stack and set current = root.
  2. Loop as long as current is not None or the stack is not empty.
    • Go Left: If current is not None:
      • Push current onto the stack.
      • Move to the left child: current = current.left.
    • Visit and Go Right: If current is None (meaning we’ve gone as far left as possible):
      • Pop a node from the stack. This is the node we need to “visit”. Process its data (e.g., add to a result list).
      • Now, move to the right subtree of the popped node: current = popped_node.right.
  3. The loop terminates when both the stack is empty and the current node is None.