Binary Tree Theory & Implementation (Java)

1. Fundamentals of Binary Trees

1.1 Basic Definitions

• Node: A fundamental part of a binary tree that stores a value and pointers to left and right children.

• Edge: Connection between parent and child node.

• Root: The topmost node in the tree.

• Parent: A node that has one or more children.

• Child: A node that descends from another node.

• Leaf: A node with no children.

• Siblings: Nodes that share the same parent.

• Ancestor: Any node on the path from the root to a given node (excluding the node).

• Descendant: Any node that lies beneath a node.

• Height: The number of edges in the longest path from the node to a leaf.

• Depth: The number of edges from the root to the node.

• Level: Nodes with the same depth are on the same level.

2. Binary Tree Node Definition in Java

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

3. Tree Construction

3.1 Insert Node (Binary Tree - Level Order)

Not BST. For binary tree (not sorted), insert at the first empty spot level-wise.

public TreeNode insert(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode curr = queue.poll();
        if (curr.left == null) {
            curr.left = new TreeNode(val);
            break;
        } else queue.add(curr.left);

        if (curr.right == null) {
            curr.right = new TreeNode(val);
            break;
        } else queue.add(curr.right);
    }
    return root;
}

Time Complexity: O(N) (worst case, full traversal)
Space Complexity: O(N) for queue

3.2 Delete Node in Binary Tree

Remove the deepest node and replace it with the target node to be deleted.

public TreeNode delete(TreeNode root, int val) {
    if (root == null) return null;
    if (root.left == null && root.right == null) {
        return root.val == val ? null : root;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    TreeNode target = null, last = null, parentOfLast = null;

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.val == val) target = node;
        if (node.left != null) {
            parentOfLast = node;
            last = node.left;
            queue.add(node.left);
        }
        if (node.right != null) {
            parentOfLast = node;
            last = node.right;
            queue.add(node.right);
        }
    }

    if (target != null) {
        target.val = last.val;
        if (parentOfLast.right == last) parentOfLast.right = null;
        else parentOfLast.left = null;
    }
    return root;
}

4. Tree Traversals

4.1 DFS - Recursive Traversals

Inorder: Left → Root → Right

void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val + " ");
    inorder(root.right);
}

Preorder: Root → Left → Right

void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorder(root.left);
    preorder(root.right);
}

Postorder: Left → Right → Root

void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.val + " ");
}

Time and Space Complexities (All)

• Time: O(N)

• Space: O(H) (recursion stack) — H = height of tree

4.2 DFS - Stack-Based Iterative Traversals

Inorder (Iterative)

void inorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        System.out.print(curr.val + " ");
        curr = curr.right;
    }
}

Preorder (Iterative)

void preorderIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode curr = stack.pop();
        System.out.print(curr.val + " ");
        if (curr.right != null) stack.push(curr.right);
        if (curr.left != null) stack.push(curr.left);
    }
}

Postorder (Two Stacks)

void postorderIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> s1 = new Stack<>();
    Stack<TreeNode> s2 = new Stack<>();
    s1.push(root);
    while (!s1.isEmpty()) {
        TreeNode node = s1.pop();
        s2.push(node);
        if (node.left != null) s1.push(node.left);
        if (node.right != null) s1.push(node.right);
    }
    while (!s2.isEmpty()) System.out.print(s2.pop().val + " ");
}

4.3 BFS - Level Order

void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode curr = queue.poll();
        System.out.print(curr.val + " ");
        if (curr.left != null) queue.add(curr.left);
        if (curr.right != null) queue.add(curr.right);
    }
}

Time Complexity: O(N)
Space Complexity: O(N)

5. Important Binary Tree Patterns

5.1 Height of Tree

int height(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(height(root.left), height(root.right));
}

5.2 Diameter of Tree (Longest Path)

int maxDiameter = 0;
int diameter(TreeNode root) {
    dfs(root);
    return maxDiameter;
}

int dfs(TreeNode node) {
    if (node == null) return 0;
    int left = dfs(node.left);
    int right = dfs(node.right);
    maxDiameter = Math.max(maxDiameter, left + right);
    return 1 + Math.max(left, right);
}

5.3 Check if Balanced

boolean isBalanced(TreeNode root) {
    return dfs(root) != -1;
}

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

5.4 Symmetric Tree

boolean isSymmetric(TreeNode root) {
    return root == null || isMirror(root.left, root.right);
}

boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null || t2 == null) return t1 == t2;
    return t1.val == t2.val && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}

6. Formulas and Observations

• Max nodes in level l: 2l−12^

• Max nodes in tree of height h: 2h−12^h - 1

• Min height for N nodes: ⌈log⁡2(N+1)⌉\lceil \log_2(N+1) \rceil

• If all nodes have 0 or 2 children, then number of leaf nodes = internal nodes + 1

7. Space & Time Complexities Summary