M.T.Ramkrushna

Posted on Oct 3

Topic 9: Trees — Binary Trees 🌳

#ai #python #dsa

Trees are one of the most important DSA topics for coding interviews and exams.

A tree is a hierarchical data structure made of nodes connected by edges.

Example:

1 is the root
2 and 3 are children of 1
4, 5, and 6 are leaf nodes
The height of this tree is 2 edges

1. Binary Tree

A binary tree is a tree where each node has at most two children:

left
right

Python representation

Python

Run

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

Creating a tree:

Python

Run

root = TreeNode(1)

root.left = TreeNode(2)
root.right = TreeNode(3)

root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

2. Tree Traversals

Traversal means visiting every node in a particular order.

The three major DFS traversals are:

Preorder
Inorder
Postorder

There is also:

Level-order traversal, using BFS

3. Preorder Traversal

Order:

Root → Left → Right

For this tree:

Preorder result:

[1, 2, 4, 5, 3]

Recursive solution

Python

Run

def preorder(root):
    result = []

    def dfs(node):
        if node is None:
            return

        result.append(node.val)
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return result

Interview pattern

Python

Run

def dfs(node):
    if node is None:
        return

    # Process current node
    dfs(node.left)
    dfs(node.right)

Preorder is useful when you need to process the parent before its children.

4. Inorder Traversal

Order:

Left → Root → Right

For the same tree:

Inorder result:

[4, 2, 5, 1, 3]

Recursive solution

Python

Run

def inorder(root):
    result = []

    def dfs(node):
        if node is None:
            return

        dfs(node.left)
        result.append(node.val)
        dfs(node.right)

    dfs(root)
    return result

Important interview fact

For a Binary Search Tree, inorder traversal gives values in sorted order.

Example BST:

Inorder:

[1, 2, 3, 4, 5, 6, 7]

5. Postorder Traversal

Order:

Left → Right → Root

Result for the tree:

[4, 5, 2, 3, 1]

Recursive solution

Python

Run

def postorder(root):
    result = []

    def dfs(node):
        if node is None:
            return

        dfs(node.left)
        dfs(node.right)
        result.append(node.val)

    dfs(root)
    return result

Postorder is useful when a node depends on the results of its children.

Examples:

Deleting a tree
Calculating subtree sizes
Calculating tree height
Dynamic programming on trees

6. Level-Order Traversal — BFS

Level-order visits nodes level by level.

Example:

Result:

[[1], [2, 3], [4, 5, 6]]

Use collections.deque as a queue.

Python

Run

from collections import deque

def level_order(root):
    if root is None:
        return []

    result = []
    queue = deque([root])

    while queue:
        level = []

        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

Complexity

Time: O(n)
Space: O(n) in the worst case

7. Maximum Depth of a Binary Tree

The depth is the number of nodes on the longest root-to-leaf path.

Example:

Maximum depth:

Recursive solution

Python

Run

def max_depth(root):
    if root is None:
        return 0

    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)

    return 1 + max(left_depth, right_depth)

Core idea

The depth of a node is:

1 + max(depth of left subtree, depth of right subtree)

This is a very common tree recursion pattern.

8. Same Tree

Given two binary trees, determine whether they are identical.

Two trees are identical if:

Their values are equal
Their left subtrees are identical
Their right subtrees are identical

Python

Run

def is_same_tree(p, q):
    if p is None and q is None:
        return True

    if p is None or q is None:
        return False

    if p.val != q.val:
        return False

    return (
        is_same_tree(p.left, q.left)
        and is_same_tree(p.right, q.right)
    )

Complexity

Time: O(n)
Space: O(h) recursion stack
h is the height of the tree

9. Invert a Binary Tree

Invert means swapping the left and right children of every node.

Before:

After:

Recursive solution

Python

Run

def invert_tree(root):
    if root is None:
        return None

    root.left, root.right = root.right, root.left

    invert_tree(root.left)
    invert_tree(root.right)

    return root

Important pattern

When the problem asks you to modify every node, consider:

Python

Run

process current node
recurse left
recurse right

10. Count Number of Nodes

Python

Run

def count_nodes(root):
    if root is None:
        return 0

    return (
        1
        + count_nodes(root.left)
        + count_nodes(root.right)
    )

The formula is:

size(tree) = 1 + size(left subtree) + size(right subtree)

11. Sum of All Nodes

Python

Run

def tree_sum(root):
    if root is None:
        return 0

    return (
        root.val
        + tree_sum(root.left)
        + tree_sum(root.right)
    )

This is another example of postorder-style tree recursion.

12. Path Sum

Determine whether there is a root-to-leaf path whose values add up to targetSum.

Example:

        5
       / \
      4   8
     /   / \
    11  13  4
   /  \      \
  7    2      1

Target:

Path:

5 → 4 → 11 → 2 = 22

Solution

Python

Run

def has_path_sum(root, target_sum):
    if root is None:
        return False

    if root.left is None and root.right is None:
        return root.val == target_sum

    remaining = target_sum - root.val

    return (
        has_path_sum(root.left, remaining)
        or has_path_sum(root.right, remaining)
    )

Important detail

A path must usually end at a leaf, not just any node.

13. Diameter of a Binary Tree

The diameter is the longest path between any two nodes.

It may or may not pass through the root.

Example:

Longest path:

4 → 2 → 1 → 3

Diameter:

3 edges

Solution

Python

Run

def diameter_of_binary_tree(root):
    diameter = 0

    def height(node):
        nonlocal diameter

        if node is None:
            return 0

        left_height = height(node.left)
        right_height = height(node.right)

        diameter = max(
            diameter,
            left_height + right_height
        )

        return 1 + max(left_height, right_height)

    height(root)
    return diameter

Why does this work?

At each node:

longest path through node
= left height + right height

We calculate the height while updating the maximum diameter.

Complexity

Time: O(n)
Space: O(h)

14. Balanced Binary Tree

A tree is height-balanced if, at every node:

abs(left height - right height) <= 1

Efficient solution

Python

Run

def is_balanced(root):
    def height(node):
        if node is None:
            return 0

        left = height(node.left)
        if left == -1:
            return -1

        right = height(node.right)
        if right == -1:
            return -1

        if abs(left - right) > 1:
            return -1

        return 1 + max(left, right)

    return height(root) != -1

Why return `-1`?

-1 acts as a signal that an unbalanced subtree has been found.

This avoids repeatedly calculating heights.

15. Iterative Inorder Traversal

Recursive traversal is easier, but interviewers may ask for an iterative version.

Python

Run

def inorder_iterative(root):
    result = []
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        result.append(current.val)

        current = current.right

    return result

Main idea

Keep moving left.
Push nodes into the stack.
Process the most recent node.
Move to its right subtree.

16. Tree Problem Recognition

Problem wording	Likely technique
Visit root, left, right	Preorder
Sorted values in BST	Inorder
Children before parent	Postorder
Level by level	BFS with deque
Maximum depth	Recursive height
Longest path	Height + global answer
Compare two trees	DFS recursion
Root-to-leaf target	DFS with remaining sum
Shortest path in unweighted tree	BFS
Modify every node	DFS
Need subtree result	Postorder

17. Binary Tree vs Binary Search Tree

A binary tree only restricts the number of children.

A Binary Search Tree, or BST, also follows:

all values in left subtree < node.val
all values in right subtree > node.val

Example:

        8
       / \
      3   10
     / \    \
    1   6    14

Searching in a balanced BST:

Average: O(log n)
Worst case: O(n)

A completely skewed BST can behave like a linked list:

18. Common Interview Mistakes

Mistake 1: Forgetting the base case

Always handle:

Python

Run

if root is None:
    ...

Mistake 2: Confusing depth and height

Depending on the problem:

Height may count edges
Height may count nodes
Read the definition carefully

Mistake 3: Using global variables incorrectly

If using a nested function:

Python

Run

nonlocal answer

is needed to modify an outer local variable.

Mistake 4: Forgetting leaf conditions

For root-to-leaf problems:

Python

Run

if node.left is None and node.right is None:

Mistake 5: Using list as a queue inefficiently

Avoid:

Python

Run

queue.pop(0)

Use:

Python

Run

from collections import deque
queue.popleft()

Must-Know Tree Templates

DFS template

Python

Run

def dfs(node):
    if node is None:
        return

    dfs(node.left)
    dfs(node.right)

Return information from children

Python

Run

def dfs(node):
    if node is None:
        return 0

    left = dfs(node.left)
    right = dfs(node.right)

    return 1 + max(left, right)

BFS template

Python

Run

from collections import deque

queue = deque([root])

while queue:
    node = queue.popleft()

    if node.left:
        queue.append(node.left)

    if node.right:
        queue.append(node.right)

Practice Questions

Try solving these in order:

Easy

Maximum Depth of Binary Tree
Same Tree
Invert Binary Tree
Count Good Nodes in Binary Tree
Binary Tree Preorder Traversal
Binary Tree Inorder Traversal
Binary Tree Postorder Traversal

Medium

Binary Tree Level Order Traversal
Path Sum
Diameter of Binary Tree
Balanced Binary Tree
Lowest Common Ancestor of a Binary Tree
Right Side View of Binary Tree
Validate Binary Search Tree

Important exam question

Implement all four traversals for this tree:

Expected answers:

Preorder:   [1, 2, 4, 5, 3, 6]
Inorder:    [4, 2, 5, 1, 3, 6]
Postorder:  [4, 5, 2, 6, 3, 1]
Level order: [[1], [2, 3], [4, 5, 6]]

Next topic: Binary Search Trees (BST), including search, insertion, deletion, validation, and lowest common ancestor.

1. Binary Tree

Python representation

2. Tree Traversals

3. Preorder Traversal

Recursive solution

Interview pattern

4. Inorder Traversal

Recursive solution

Important interview fact

5. Postorder Traversal

Recursive solution

6. Level-Order Traversal — BFS

Complexity

7. Maximum Depth of a Binary Tree

Recursive solution

Core idea

8. Same Tree

Complexity

9. Invert a Binary Tree

Recursive solution

Important pattern

10. Count Number of Nodes

11. Sum of All Nodes

12. Path Sum

Solution

Important detail

13. Diameter of a Binary Tree

Solution

Why does this work?

Complexity

14. Balanced Binary Tree

Efficient solution

Why return -1?

15. Iterative Inorder Traversal

Main idea

16. Tree Problem Recognition

17. Binary Tree vs Binary Search Tree

18. Common Interview Mistakes

Mistake 1: Forgetting the base case

Mistake 2: Confusing depth and height

Mistake 3: Using global variables incorrectly

Mistake 4: Forgetting leaf conditions

Mistake 5: Using list as a queue inefficiently

Must-Know Tree Templates

DFS template

Return information from children

BFS template

Practice Questions

Easy

Medium

Important exam question

Why return `-1`?