Home/Learn/DSA/Trees & Binary Search Trees

Trees & Binary Search Trees

Intermediate

Hierarchical data structure at the heart of databases, file systems, and half of all interview problems.

Think of it this way

Think of a company org chart. The CEO is at the top — the root. Each manager can have up to two direct reports (binary tree). A BST adds one rule: smaller employee IDs go left, bigger ones go right. That lets you find anyone in O(log n) steps instead of checking every person. Java's TreeMap works exactly this way internally.

In code, it looks like thisJava
class TreeNode {
    int val;
    TreeNode left;   // smaller values live here
    TreeNode right;  // larger values live here
    TreeNode(int val) { this.val = val; }
}
//        5          ← root
//       / \
//      3   8        ← 3 < 5 goes left, 8 > 5 goes right
//     / \
//    2   4          ← BST property holds at every node

Overview

A binary tree has at most two children per node (left, right). A Binary Search Tree (BST) adds the invariant: left subtree values < root < right subtree values. This ordering allows O(log n) search in balanced trees. Tree problems almost always have elegant recursive solutions. The key is understanding the four traversals (inorder, preorder, postorder, level-order) and when to use each.

Time & Space Complexity

Operation Time Space
Search (balanced BST)O(log n)O(h)
Search (skewed tree)O(n)O(n)
Insert (balanced BST)O(log n)O(h)
Delete (balanced BST)O(log n)O(h)
Inorder traversalO(n)O(h)
Height calculationO(n)O(h)

Java Implementation

Java
public class BinaryTree {

    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    // Inorder traversal (Left → Root → Right) — O(n)
    public static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    // Height of binary tree — O(n)
    public static int height(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(height(root.left), height(root.right));
    }

    // Check if tree is balanced — O(n)
    public static boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }

    private static int checkHeight(TreeNode node) {
        if (node == null) return 0;
        int left = checkHeight(node.left);
        if (left == -1) return -1;
        int right = checkHeight(node.right);
        if (right == -1) return -1;
        if (Math.abs(left - right) > 1) return -1;
        return 1 + Math.max(left, right);
    }

    // Lowest Common Ancestor in a BST — O(log n)
    public static TreeNode lcaBST(TreeNode root, int p, int q) {
        if (root == null) return null;
        if (p < root.val && q < root.val) return lcaBST(root.left, p, q);
        if (p > root.val && q > root.val) return lcaBST(root.right, p, q);
        return root; // split point — this is the LCA
    }

    // Maximum path sum in a binary tree — O(n)
    private static int maxSum = Integer.MIN_VALUE;

    public static int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        gainFrom(root);
        return maxSum;
    }

    private static int gainFrom(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, gainFrom(node.left));
        int right = Math.max(0, gainFrom(node.right));
        maxSum = Math.max(maxSum, node.val + left + right);
        return node.val + Math.max(left, right);
    }
}

Key Points to Remember

  • Inorder traversal of a BST gives elements in sorted order
    void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);          // go left first
    System.out.print(node.val);  // visit root
    inorder(node.right);         // then right
}
// Result on BST: 2, 3, 4, 5, 8 — always sorted!
  • Height of a balanced tree is O(log n); a skewed tree degrades to O(n) — like a linked list
  • LCA (Lowest Common Ancestor) is a very common interview pattern
    // In a BST: if both values are less than root, go left; if both greater, go right
if (p < root.val && q < root.val) return lca(root.left, p, q);
if (p > root.val && q > root.val) return lca(root.right, p, q);
return root; // split point — this node IS the LCA
  • Serialization/deserialization tests deep understanding — you must reconstruct the exact tree from a string
  • AVL and Red-Black trees self-balance to keep O(log n); Java's TreeMap uses Red-Black internally
    TreeMap<Integer, String> sorted = new TreeMap<>(); // keys always in sorted order
sorted.put(5, "five");
sorted.put(2, "two");
System.out.println(sorted.firstKey()); // 2 — O(log n)

Interview Questions

Sign in to ask Aria
1

Validate if a Binary Search Tree is valid

MediumAmazonSolve it
2

Lowest Common Ancestor of two nodes

MediumFacebookSolve it
3

Serialize and deserialize a binary tree

HardGoogleSolve it
4

Binary tree maximum path sum

HardAmazonSolve it
5

Construct binary tree from preorder and inorder traversal

MediumMicrosoftSolve it

Ask Aria about Trees & Binary Search Trees

Your personal AI tutor — ask anything about this concept

Previous
Queue
Next
Graphs