DSA From Zero to Job-ReadyLesson 11 of 28

Lessons

1 · Foundations (Think Like a Programmer)

2 · Data Structures and Recursion

3 · Core Algorithms and Reusable Patterns

4 · Advanced Interview Topics

5 · From Practice to Job-Ready

Lesson 11 of 28

Lesson 11 · Data Structures and Recursion

Trees and Binary Search Trees

Tree vocabulary, the four traversals (preorder, inorder, postorder, level-order), recursive and iterative code, and binary search trees: search, insert, and the right way to validate one.

By Karthikeyan A22 min readTechnology

For

Learners who understand recursion and linked lists and are ready for hierarchical data, which is a staple of coding interviews.

Level

Intermediate

Before you start

Articles 7, 8 and 10: linked lists, stacks and queues, and recursion. The call stack idea matters a lot here.

On this page

Key takeaways

A binary tree node has a value and up to two children. Almost every tree problem is solved by handling null, then combining the answers from the left and right subtrees.
Preorder visits the root first, inorder visits it between its subtrees, postorder visits it last, and level-order goes level by level using a queue.
In a binary search tree, everything in the left subtree is smaller than the node and everything in the right is larger. Inorder traversal of a BST is sorted.
BST search and insert take O(h) time, where h is the height. That is O(log n) when the tree is balanced and O(n) when it degenerates into a line.
To validate a BST, pass down a valid range for each node. Comparing a node only with its direct children is wrong.

Your computer's folders form a tree. There is one top folder, it contains folders, those contain more folders and files, and so on. An organisation chart is a tree. So is a family tree, the structure of this very article (headings under headings), and the way a company's menu categories branch.

A tree is a hierarchy of nodes. It is the first structure in this course where each element can lead to several others, and it is the foundation for heaps, tries, graphs and much of dynamic programming. The good news: you already know the tools. A tree is recursive by nature (each part of a tree is itself a smaller tree), so the recursion from the previous article fits perfectly.

What you will learn

Tree vocabulary: root, leaf, height, depth, subtree.
How to represent a binary tree in Java.
Preorder, inorder, postorder and level-order traversal, recursive and iterative.
How to compute height, size and leaf count.
What a binary search tree is, and how to search, insert and validate one.
When tree operations are fast, and when they are not.

Tree vocabulary

Code

            1            <- root (no parent)           / \          2   3          <- 2 and 3 are siblings, children of 1         / \   \        4   5   6        <- 4, 5, 6 are leaves (no children)

Term	Meaning	In the picture
Node	One element of the tree	Each number
Edge	A link from a parent to a child	The lines
Root	The top node, the only one with no parent	`1`
Parent / child	A node and the nodes directly below it	`2` is the parent of `4` and `5`
Leaf	A node with no children	`4`, `5`, `6`
Subtree	A node together with everything below it	The subtree rooted at `2` is `2, 4, 5`
Depth of a node	Number of edges from the root to the node	Depth of `1` is 0, of `2` is 1, of `4` is 2
Height of a node	Number of edges on the longest path down to a leaf	Height of `4` is 0, of `2` is 1, of `1` is 2
Height of the tree	Height of the root	2
Level	All nodes at the same depth	Level 2 is `4, 5, 6`

A binary tree is a tree in which every node has at most two children, called the left child and the right child.

Representing a binary tree in Java

Java

static class Node {    int val;    Node left;     // null means "no left child"    Node right;    Node(int val) {        this.val = val;    }}

You keep a reference to the root. An empty tree is root == null. A leaf has both left and right equal to null.

The recursive pattern for trees

A tree is either empty, or a root with a left subtree and a right subtree, and each subtree is itself a tree. So most tree methods have this shape:

Code

solve(node):    if node is null: return the answer for an empty tree   // base case    leftAnswer  = solve(node.left)    rightAnswer = solve(node.right)    return combine(node.val, leftAnswer, rightAnswer)

By the leap of faith from the recursion article, you assume solve works on the two smaller subtrees, and just combine. For the height, the combination is "1 plus the larger of the two heights". For the size, it is "1 plus the sizes of both". We will write both.

Traversals

To traverse a tree is to visit every node. There are four standard orders. The first three are depth-first: they go down a branch as far as possible before moving on. They differ only in when the node itself is visited relative to its subtrees.

Traversal	Order	Typical use
Preorder	node, left, right	Copying a tree, serialising it, printing a hierarchy
Inorder	left, node, right	Reading a BST in sorted order
Postorder	left, right, node	Computing something from the children first (size, height, deleting a tree)
Level-order	level by level, left to right	Shortest distance from the root, printing by level

For the tree above (1 with children 2 and 3, 2 with children 4 and 5, 3 with a right child 6):

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

Why do the orders differ? In preorder we say "hello" to the node on the way down. In inorder we say it after finishing the whole left side. In postorder we say it on the way back up, after both sides are done. It is the same walk through the tree, and only the moment of the add call changes.

Level-order uses a queue: take a node from the front, visit it, and add its children to the back. Because children are added behind everything already waiting, nodes are processed level by level. To report each level separately, process exactly queue.size() nodes at the start of each round: those are the nodes of the current level.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queue;public class Main {    static class Node {        int val;        Node left;        Node right;        Node(int val) {            this.val = val;        }    }    static void preorder(Node node, List<Integer> out) {        if (node == null) {            return;        }        out.add(node.val);               // visit before the subtrees        preorder(node.left, out);        preorder(node.right, out);    }    static void inorder(Node node, List<Integer> out) {        if (node == null) {            return;        }        inorder(node.left, out);        out.add(node.val);               // visit between the subtrees        inorder(node.right, out);    }    static void postorder(Node node, List<Integer> out) {        if (node == null) {            return;        }        postorder(node.left, out);        postorder(node.right, out);        out.add(node.val);               // visit after the subtrees    }    static List<List<Integer>> levelOrder(Node root) {        List<List<Integer>> levels = new ArrayList<>();        if (root == null) {            return levels;        }        Queue<Node> queue = new ArrayDeque<>();        queue.offer(root);        while (!queue.isEmpty()) {            int count = queue.size();                 // how many nodes are on this level            List<Integer> level = new ArrayList<>();            for (int i = 0; i < count; i++) {                Node node = queue.poll();                level.add(node.val);                if (node.left != null) {                    queue.offer(node.left);                }                if (node.right != null) {                    queue.offer(node.right);                }            }            levels.add(level);        }        return levels;    }    static int height(Node node) {                    // in edges: empty tree is -1, a leaf is 0        if (node == null) {            return -1;        }        return 1 + Math.max(height(node.left), height(node.right));    }    static int size(Node node) {        if (node == null) {            return 0;        }        return 1 + size(node.left) + size(node.right);    }    static int countLeaves(Node node) {        if (node == null) {            return 0;        }        if (node.left == null && node.right == null) {            return 1;        }        return countLeaves(node.left) + countLeaves(node.right);    }    public static void main(String[] args) {        Node root = new Node(1);        root.left = new Node(2);        root.right = new Node(3);        root.left.left = new Node(4);        root.left.right = new Node(5);        root.right.right = new Node(6);        List<Integer> pre = new ArrayList<>();        List<Integer> in = new ArrayList<>();        List<Integer> post = new ArrayList<>();        preorder(root, pre);        inorder(root, in);        postorder(root, post);        System.out.println("preorder:    " + pre);        System.out.println("inorder:     " + in);        System.out.println("postorder:   " + post);        System.out.println("level-order: " + levelOrder(root));        System.out.println("height=" + height(root) + " size=" + size(root) + " leaves=" + countLeaves(root));        System.out.println("empty tree: height=" + height(null) + " size=" + size(null) + " levels=" + levelOrder(null));    }}

Code

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]]height=2 size=6 leaves=3empty tree: height=-1 size=0 levels=[]

Compare the printed lists with the ones we worked out by hand. Matching them is a good test of your understanding.

Complexity of traversals and tree recursion

Each node is visited once and does constant work, so the time is O(n) for n nodes. The extra space is the recursion stack, which is as deep as the height h of the tree: O(h). For a well-balanced tree h is about log2(n). For a tree that is one long chain, h is n - 1, so the stack can reach O(n), and a very deep tree can overflow Java's stack. Level-order uses a queue that can hold up to one whole level, which for a complete tree is about n / 2 nodes, so O(n) space in the worst case.

Iterative inorder traversal

Recursion uses the call stack for you. You can do the same walk with your own stack. This matters when the tree could be very deep, or when an interviewer asks "can you do it without recursion?".

The idea: keep going left, remembering every node you pass on a stack. When you can go no further left, pop a node, visit it, and then move to its right child and repeat.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.ArrayList;import java.util.Deque;import java.util.List;public class Main {    static class Node {        int val;        Node left;        Node right;        Node(int val) {            this.val = val;        }    }    static List<Integer> inorderIterative(Node root) {        List<Integer> out = new ArrayList<>();        Deque<Node> stack = new ArrayDeque<>();        Node cur = root;        while (cur != null || !stack.isEmpty()) {            while (cur != null) {          // go as far left as possible, remembering the path                stack.push(cur);                cur = cur.left;            }            cur = stack.pop();             // the most recent node with nothing further left            out.add(cur.val);              // visit it            cur = cur.right;               // then handle its right subtree        }        return out;    }    static List<Integer> preorderIterative(Node root) {        List<Integer> out = new ArrayList<>();        if (root == null) {            return out;        }        Deque<Node> stack = new ArrayDeque<>();        stack.push(root);        while (!stack.isEmpty()) {            Node node = stack.pop();            out.add(node.val);            if (node.right != null) {      // push right first so that left is popped first                stack.push(node.right);            }            if (node.left != null) {                stack.push(node.left);            }        }        return out;    }    public static void main(String[] args) {        Node root = new Node(1);        root.left = new Node(2);        root.right = new Node(3);        root.left.left = new Node(4);        root.left.right = new Node(5);        root.right.right = new Node(6);        System.out.println(inorderIterative(root));        System.out.println(preorderIterative(root));        System.out.println(inorderIterative(null));    }}

Code

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

Dry run of the iterative inorder on our tree:

Action	`cur`	Stack (top first)	Output so far
Go left from `1`	`1` then `2` then `4` then `null`	`4, 2, 1`
Pop and visit	`4` (then `cur = 4.right = null`)	`2, 1`	`4`
Pop and visit	`2` (then `cur = 5`)	`1`	`4 2`
Go left from `5`	`5` then `null`	`5, 1`	`4 2`
Pop and visit	`5` (then `cur = null`)	`1`	`4 2 5`
Pop and visit	`1` (then `cur = 3`)	empty	`4 2 5 1`
Go left from `3`	`3` then `null`	`3`	`4 2 5 1`
Pop and visit	`3` (then `cur = 6`)	empty	`4 2 5 1 3`
Go left from `6`, pop	`6`, then `cur = null`	empty	`4 2 5 1 3 6`

The loop ends because cur is null and the stack is empty. Time is O(n) and the stack holds at most h nodes.

Binary search trees

A binary search tree (BST) is a binary tree with an ordering rule:

For every node, all values in its left subtree are smaller than the node's value, and all values in its right subtree are larger.

(We assume no duplicates here. Real implementations must choose a rule for duplicates, such as ignoring them or counting them.)

Code

          8        /   \       3     10      / \      \     1   6      14        / \     /       4   7   13

Notice that this rule lets us discard half of the remaining tree at every step. Look for 7: compare with 8. 7 < 8, so go left, and the whole right subtree (10, 14, 13) is irrelevant. At 3, 7 > 3, so go right, and 1 is irrelevant. At 6, 7 > 6, go right: found. This is binary search, but on a pointer structure.

Search

Code

search(node, target):    if node is null: not found    if target == node.val: found    if target < node.val: search(node.left, target)    else: search(node.right, target)

Because each step goes down one level, the cost is at most the height of the tree: O(h).

Insert

To insert a value, search for it. When you fall off the tree (reach null), that empty spot is exactly where the new node belongs. A neat recursive way: insert returns the root of the (possibly updated) subtree, and each caller stores the result back into its child pointer.

Inorder gives sorted order

Inorder visits left, node, right. In a BST, everything on the left is smaller and everything on the right is larger, so inorder visits the values in increasing order. This is a very useful fact: it turns "kth smallest", "validate a BST" and "convert to a sorted list" into inorder problems.

Deleting a node (the idea)

Deletion has three cases. A leaf can simply be removed. A node with one child is replaced by that child. A node with two children is replaced by its inorder successor (the smallest node in its right subtree), or its predecessor, and then that successor node is removed from where it was. We do not code it here, but you should be able to explain it.

Java

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    static class Node {        int val;        Node left;        Node right;        Node(int val) {            this.val = val;        }    }    static Node insert(Node node, int value) {        if (node == null) {            return new Node(value);                   // found the empty spot        }        if (value < node.val) {            node.left = insert(node.left, value);     // store the result back        } else if (value > node.val) {            node.right = insert(node.right, value);        }                                             // equal: ignore the duplicate        return node;    }    static boolean contains(Node root, int target) {        Node cur = root;        while (cur != null) {            if (target == cur.val) {                return true;            }            cur = target < cur.val ? cur.left : cur.right;        }        return false;    }    static void inorder(Node node, List<Integer> out) {        if (node == null) {            return;        }        inorder(node.left, out);        out.add(node.val);        inorder(node.right, out);    }    static int height(Node node) {        return node == null ? -1 : 1 + Math.max(height(node.left), height(node.right));    }    // Wrong idea: only compares each node with its direct children.    static boolean looksValidLocally(Node node) {        if (node == null) {            return true;        }        if (node.left != null && node.left.val >= node.val) {            return false;        }        if (node.right != null && node.right.val <= node.val) {            return false;        }        return looksValidLocally(node.left) && looksValidLocally(node.right);    }    // Right idea: every node must lie strictly between the bounds inherited from its ancestors.    static boolean isValidBst(Node node, long low, long high) {        if (node == null) {            return true;        }        if (node.val <= low || node.val >= high) {            return false;        }        return isValidBst(node.left, low, node.val) && isValidBst(node.right, node.val, high);    }    static boolean isValidBst(Node root) {        return isValidBst(root, Long.MIN_VALUE, Long.MAX_VALUE);    }    static Node buildFrom(int... values) {        Node root = null;        for (int v : values) {            root = insert(root, v);        }        return root;    }    public static void main(String[] args) {        Node bst = buildFrom(8, 3, 10, 1, 6, 14, 4, 7, 13);        List<Integer> sorted = new ArrayList<>();        inorder(bst, sorted);        System.out.println(sorted);        System.out.println(contains(bst, 6) + " " + contains(bst, 5) + " " + height(bst));        System.out.println(isValidBst(bst));        Node bad = new Node(5);              // 5 with left child 3, and 3 has a right child 6        bad.left = new Node(3);        bad.left.right = new Node(6);        System.out.println(looksValidLocally(bad) + " " + isValidBst(bad));        Node sortedInsert = buildFrom(1, 2, 3, 4, 5, 6, 7);        Node balancedInsert = buildFrom(4, 2, 6, 1, 3, 5, 7);        System.out.println("height after sorted inserts: " + height(sortedInsert) + ", after balanced order: " + height(balancedInsert));        Node extremes = buildFrom(0, Integer.MIN_VALUE, Integer.MAX_VALUE);        System.out.println(isValidBst(extremes));    }}

Code

[1, 3, 4, 6, 7, 8, 10, 13, 14]true false 3truetrue falseheight after sorted inserts: 6, after balanced order: 2true

Why validation needs ranges

The tree bad above has root 5, left child 3, and 3 has a right child 6. Look at each node and its direct children: 3 < 5 is fine; 6 > 3 is fine. A local check says "valid". But 6 is in the left subtree of 5, so it must be smaller than 5. It is not, so the tree is not a BST.

The correct check carries a range down the recursion. The root may be anything. Going left, the node must be below the parent's value (the upper bound shrinks to the parent). Going right, it must be above the parent's value (the lower bound rises). Every node must be strictly inside the range inherited from all of its ancestors.

Dry run on bad:

Node	Allowed range (low, high)	Value	Inside?
`5`	(-infinity, +infinity)	5	yes
`3` (left of 5)	(-infinity, 5)	3	yes
`6` (right of 3)	(3, 5)	6	no, 6 is not below 5

The check fails exactly where the local check could not see. We use long bounds so that the values Integer.MIN_VALUE and Integer.MAX_VALUE are still valid (the last test above), which a bound of type int could not do cleanly. An alternative way to validate is to run an inorder traversal and check that the output is strictly increasing.

Shape and speed

The cost of search and insert is O(h), where h is the height. That is the whole story, and the height depends on the order of insertion. Inserting 1, 2, 3, 4, 5, 6, 7 in sorted order makes each new node the right child of the previous one: the tree becomes a chain, h = n - 1, and operations cost O(n). Inserting the same values as 4, 2, 6, 1, 3, 5, 7 gives a perfectly balanced tree with h = 2. The program printed 6 and 2.

The cure is a self-balancing BST (such as an AVL tree or a red-black tree) which rearranges itself after insertions and deletions to keep the height near log2(n). You will not usually implement one. Java's TreeMap and TreeSet are red-black trees, which is why their operations are O(log n).

Tree	Height with `n` nodes	Search / insert
Balanced	about `log2(n)`	O(log n)
Skewed (a chain)	`n - 1`	O(n)
Self-balancing (`TreeMap`)	kept near `log2(n)`	O(log n) guaranteed

Complexity summary

Task	Time	Extra space
Any traversal (recursive)	O(n)	O(h) call stack
Iterative inorder or preorder	O(n)	O(h) explicit stack
Level-order	O(n)	O(w), where `w` is the maximum width, which can be O(n)
Height, size, leaf count	O(n)	O(h)
BST search, insert	O(h): O(log n) balanced, O(n) skewed	O(1) iterative, O(h) recursive
BST validation with ranges	O(n)	O(h)

Edge cases and common mistakes

Forgetting the null base case. Every tree method must handle null. It is also the empty tree.
Confusing height in edges with height in nodes. State your convention.
Dropping the result of a recursive insert. insert(node.left, v) alone loses the new node; assign node.left = insert(node.left, v).
Validating a BST with only local comparisons. Use ranges, or check that an inorder traversal is increasing.
Using int bounds. Integer.MIN_VALUE and Integer.MAX_VALUE are legal values, so use long or Integer objects that can be null.
Assuming a BST is balanced. A sorted input produces a chain.
Duplicates. Decide whether duplicates are rejected, go left, go right, or are counted.
Recursion depth on a skewed tree. A chain of 100,000 nodes can overflow the stack. Use an iterative version.
Mixing up the traversals. Remember: pre means the node comes before its subtrees, post means after, and in means between.

Exercises

Exercise 1

Trace

For this tree, write the preorder, inorder, postorder and level-order traversals.

Code

        7       / \      3   9     /   / \    1   8   10

Is it a valid BST? What do you notice about its inorder traversal?

Exercise 2: Invert a binary tree

Swap the left and right children of every node, so that the tree becomes its own mirror image. Show the level-order before and after for the tree with root 4, children 2 and 7, and grandchildren 1, 3, 6, 9.

Exercise 3: Lowest common ancestor in a BST

Given a BST and two values p and q that are both in the tree, find their lowest common ancestor: the deepest node that has both of them in its subtree (a node counts as its own descendant). Use the BST ordering to do it in O(h) time and O(1) extra space.

Exercise 4: Debug

This insertion method is called with 5, 3, 8, 1, 4. Find out what the tree looks like afterwards, why, and fix it.

Java

static Node insertBuggy(Node root, int v) {    if (root == null) {        return new Node(v);    }    if (v < root.val) {        insertBuggy(root.left, v);    } else {        insertBuggy(root.right, v);    }    return root;}

Exercise 5: Interview-style, the k-th smallest element

Given the root of a BST and k (counting from 1), return the k-th smallest value, or report that there is none if k is larger than the number of nodes. Stop as soon as you have the answer.

Show solutionHide solution

Preorder (node, left, right): 7 3 1 9 8 10
Inorder (left, node, right): 1 3 7 8 9 10
Postorder (left, right, node): 1 3 8 10 9 7
Level-order: 7 | 3 9 | 1 8 10

It is a valid BST: for 7, the left subtree values 3, 1 are below it and the right subtree values 9, 8, 10 are above it; for 9, the left 8 is below and the right 10 is above. The inorder traversal is sorted, as it always is for a BST.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queue;public class Main {    static class Node {        int val;        Node left;        Node right;        Node(int val, Node left, Node right) {            this.val = val;            this.left = left;            this.right = right;        }    }    static void pre(Node n, List<Integer> out) {        if (n == null) {            return;        }        out.add(n.val);        pre(n.left, out);        pre(n.right, out);    }    static void in(Node n, List<Integer> out) {        if (n == null) {            return;        }        in(n.left, out);        out.add(n.val);        in(n.right, out);    }    static void post(Node n, List<Integer> out) {        if (n == null) {            return;        }        post(n.left, out);        post(n.right, out);        out.add(n.val);    }    static List<Integer> level(Node root) {        List<Integer> out = new ArrayList<>();        Queue<Node> queue = new ArrayDeque<>();        queue.offer(root);        while (!queue.isEmpty()) {            Node n = queue.poll();            out.add(n.val);            if (n.left != null) {                queue.offer(n.left);            }            if (n.right != null) {                queue.offer(n.right);            }        }        return out;    }    public static void main(String[] args) {        Node root = new Node(7,                new Node(3, new Node(1, null, null), null),                new Node(9, new Node(8, null, null), new Node(10, null, null)));        List<Integer> a = new ArrayList<>();        List<Integer> b = new ArrayList<>();        List<Integer> c = new ArrayList<>();        pre(root, a);        in(root, b);        post(root, c);        System.out.println(a + " " + b + " " + c + " " + level(root));    }}

Code

[7, 3, 1, 9, 8, 10] [1, 3, 7, 8, 9, 10] [1, 3, 8, 10, 9, 7] [7, 3, 9, 1, 8, 10]

Exercise 2

Show solutionHide solution

Recursively: invert the left subtree, invert the right subtree, then swap the two children. The base case is null. Time O(n), stack space O(h). The order of the swap and the recursive calls does not matter, as long as every node swaps its children exactly once.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queue;public class Main {    static class Node {        int val;        Node left;        Node right;        Node(int val, Node left, Node right) {            this.val = val;            this.left = left;            this.right = right;        }    }    static Node invert(Node node) {        if (node == null) {            return null;        }        Node leftInverted = invert(node.left);        Node rightInverted = invert(node.right);        node.left = rightInverted;                 // swap        node.right = leftInverted;        return node;    }    static List<List<Integer>> levels(Node root) {        List<List<Integer>> result = new ArrayList<>();        if (root == null) {            return result;        }        Queue<Node> queue = new ArrayDeque<>();        queue.offer(root);        while (!queue.isEmpty()) {            int count = queue.size();            List<Integer> level = new ArrayList<>();            for (int i = 0; i < count; i++) {                Node n = queue.poll();                level.add(n.val);                if (n.left != null) {                    queue.offer(n.left);                }                if (n.right != null) {                    queue.offer(n.right);                }            }            result.add(level);        }        return result;    }    public static void main(String[] args) {        Node root = new Node(4,                new Node(2, new Node(1, null, null), new Node(3, null, null)),                new Node(7, new Node(6, null, null), new Node(9, null, null)));        System.out.println(levels(root));        invert(root);        System.out.println(levels(root));        System.out.println(invert(null));    }}

Code

[[4], [2, 7], [1, 3, 6, 9]][[4], [7, 2], [9, 6, 3, 1]]null

Exercise 3

Show solutionHide solution

Start at the root. If both p and q are smaller than the current node, the answer must be in the left subtree, so go left. If both are larger, go right. Otherwise, they are on different sides of the current node (or one of them equals it), so this node is where their paths split, and it is the lowest common ancestor.

Each step goes down one level, so the time is O(h), and a loop uses O(1) space.

Java

// File: Main.javapublic class Main {    static class Node {        int val;        Node left;        Node right;        Node(int val) {            this.val = val;        }    }    static Node insert(Node node, int value) {        if (node == null) {            return new Node(value);        }        if (value < node.val) {            node.left = insert(node.left, value);        } else if (value > node.val) {            node.right = insert(node.right, value);        }        return node;    }    static int lowestCommonAncestor(Node root, int p, int q) {        Node cur = root;        while (cur != null) {            if (p < cur.val && q < cur.val) {                cur = cur.left;            } else if (p > cur.val && q > cur.val) {                cur = cur.right;            } else {                return cur.val;            }        }        throw new IllegalArgumentException("empty tree");    }    public static void main(String[] args) {        Node root = null;        for (int v : new int[] {6, 2, 8, 0, 4, 7, 9, 3, 5}) {            root = insert(root, v);        }        System.out.println(lowestCommonAncestor(root, 2, 8));        System.out.println(lowestCommonAncestor(root, 2, 4));        System.out.println(lowestCommonAncestor(root, 3, 5));        System.out.println(lowestCommonAncestor(root, 7, 9));        System.out.println(lowestCommonAncestor(root, 5, 5));    }}

Code

For 3 and 5: both are below 6, so go left to 2. Both are above 2, so go right to 4. Now 3 < 4 < 5, so they split, and the answer is 4. For a node and itself (5, 5), the search reaches 5 and then stops, because neither condition holds there.

Exercise 4

Show solutionHide solution

The bug is that the result of the recursive call is ignored. When root.left is null, insertBuggy(root.left, v) creates a new node, returns it, and the caller throws it away. The new node is never attached to the tree. So after inserting 5, 3, 8, 1, 4, the tree contains only the root 5.

The fix is to store the returned node: root.left = insert(root.left, v) and root.right = insert(root.right, v).

Java

// File: Main.javapublic class Main {    static class Node {        int val;        Node left;        Node right;        Node(int val) {            this.val = val;        }    }    static Node insertBuggy(Node root, int v) {        if (root == null) {            return new Node(v);        }        if (v < root.val) {            insertBuggy(root.left, v);        } else {            insertBuggy(root.right, v);        }        return root;    }    static Node insertFixed(Node root, int v) {        if (root == null) {            return new Node(v);        }        if (v < root.val) {            root.left = insertFixed(root.left, v);        } else {            root.right = insertFixed(root.right, v);        }        return root;    }    static int size(Node n) {        return n == null ? 0 : 1 + size(n.left) + size(n.right);    }    public static void main(String[] args) {        Node buggy = null;        Node fixed = null;        for (int v : new int[] {5, 3, 8, 1, 4}) {            buggy = insertBuggy(buggy, v);            fixed = insertFixed(fixed, v);        }        System.out.println("buggy size " + size(buggy) + ", fixed size " + size(fixed));    }}

Code

buggy size 1, fixed size 5

Exercise 5

Show solutionHide solution

Inorder traversal visits a BST in increasing order, so the k-th node visited is the k-th smallest. Use the iterative inorder from the article, count visited nodes, and return as soon as the count reaches k. We never walk the whole tree.

Time is O(h + k): h steps to reach the leftmost node, then k visits. Extra space is O(h) for the stack. If k is larger than the number of nodes, the loop ends without a result, and we return null.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.Deque;public class Main {    static class Node {        int val;        Node left;        Node right;        Node(int val) {            this.val = val;        }    }    static Node insert(Node node, int value) {        if (node == null) {            return new Node(value);        }        if (value < node.val) {            node.left = insert(node.left, value);        } else if (value > node.val) {            node.right = insert(node.right, value);        }        return node;    }    static Integer kthSmallest(Node root, int k) {        Deque<Node> stack = new ArrayDeque<>();        Node cur = root;        int seen = 0;        while (cur != null || !stack.isEmpty()) {            while (cur != null) {                stack.push(cur);                cur = cur.left;            }            cur = stack.pop();            seen++;            if (seen == k) {                return cur.val;                 // stop early            }            cur = cur.right;        }        return null;                            // fewer than k nodes    }    public static void main(String[] args) {        Node root = null;        for (int v : new int[] {5, 3, 6, 2, 4, 1}) {            root = insert(root, v);        }        System.out.println(kthSmallest(root, 1) + " " + kthSmallest(root, 3) + " " + kthSmallest(root, 6) + " " + kthSmallest(root, 7));        System.out.println(kthSmallest(null, 1));    }}

Code

1 3 6 nullnull

Where to go next

Next: Heaps and Priority Queues use a tree shape stored in an array, to always find the smallest or largest element quickly. We also explain how a heap differs from a BST.
Later: a tree is a graph with no cycles. Graphs: Representations, BFS, and DFS generalises the level-order and depth-first ideas you just learned. Tries are trees for strings.
Practice habit: before you code any tree problem, ask three questions: what is the answer for null, what do I need from the left and right subtrees, and how do I combine them?

Connected lessons

References

Show all 6 →

Linked from 2 guides

Other pages in the library that point here.

Trees and Binary Search Trees

For

Level

Before you start

Key takeaways

What you will learn

Tree vocabulary

Representing a binary tree in Java

The recursive pattern for trees

Traversals

Complexity of traversals and tree recursion

Iterative inorder traversal

Binary search trees

Search

Insert

Inorder gives sorted order

Deleting a node (the idea)

Why validation needs ranges

Shape and speed

Complexity summary

Edge cases and common mistakes

Exercises

Trace

Exercise 2: Invert a binary tree

Exercise 3: Lowest common ancestor in a BST

Exercise 4: Debug

Exercise 5: Interview-style, the k-th smallest element

Where to go next

Connected lessons

Linked from 2 guides

Keep reading

How to Learn Data Structures and Algorithms Without Burning Out

The OA Landscape: Platforms, Formats, Proctoring and Rules

A LinkedIn Profile That Gets Recruiter Messages