Using Trees

Not Started

A tree is a hierarchical data structure made up of nodes. Each node contains a value and pointers to its children. The top node is called the root. Nodes with no children are called leaves.

Here, we are focussing on binary trees - trees where each node has at most two children; a left child and a right child. Binary trees are processed recursively - solve for the left subtree, solve for the right subtree, then combine the results.

When to Use

Path problems: Find or collect paths from root to leaf. Recurse downward, tracking a running sum or building a path list. Backtrack when returning.

Height / depth: Compute height as 1 + max(left, right). Base case: null returns -1 (edges) or 0 (nodes), depending on the definition.

Validation: Check if a tree satisfies a property (e.g. BST). Pass constraints (min/max bounds) down, or use in-order traversal (as seen in this week's lecture) to verify sorted order.

Traversal order: Pre-order (node, left, right) for copying. In-order (left, node, right) for sorted output from BSTs. Post-order (left, right, node) for bottom-up computation.

Define a Node

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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int x) { val = x; }
}

public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

Recursive DFS (Depth-First)

def dfs(node):
    if node is None:
        return  # base case
    # process node.val here (pre-order)
    dfs(node.left)
    # process node.val here (in-order)
    dfs(node.right)
    # process node.val here (post-order)

void dfs(TreeNode* node) {
    if (!node) return;  // base case
    // process node->val here (pre-order)
    dfs(node->left);
    // process node->val here (in-order)
    dfs(node->right);
    // process node->val here (post-order)
}

void Dfs(TreeNode node) {
    if (node == null) return;  // base case
    // process node.val here (pre-order)
    Dfs(node.left);
    // process node.val here (in-order)
    Dfs(node.right);
    // process node.val here (post-order)
}

void dfs(TreeNode node) {
    if (node == null) return;  // base case
    // process node.val here (pre-order)
    dfs(node.left);
    // process node.val here (in-order)
    dfs(node.right);
    // process node.val here (post-order)
}

Get Height

def height(node):
    if node is None:
        return -1  # no edges below null
    return 1 + max(height(node.left), height(node.right))

int height(TreeNode* node) {
    if (!node) return -1;  // no edges below null
    return 1 + max(height(node->left), height(node->right));
}

int Height(TreeNode node) {
    if (node == null) return -1;  // no edges below null
    return 1 + Math.Max(Height(node.left), Height(node.right));
}

int height(TreeNode node) {
    if (node == null) return -1;  // no edges below null
    return 1 + Math.max(height(node.left), height(node.right));
}

Check if Leaf

if not node.left and not node.right:  # leaf node
    print("leaf")

if (!node->left && !node->right)  // leaf node
    cout << "leaf";

if (node.left == null && node.right == null)  // leaf node
    Console.WriteLine("leaf");

if (node.left == null && node.right == null)  // leaf node
    System.out.println("leaf");