What is a Binary Tree?

• Node – the basic unit holding a value and references to its left and right children.
• Root – the single topmost node; the entry point into the tree.
• Leaf – a node with both children null; it has no descendants.
• Height – the length of the longest path from the root to a leaf.
• Branching limit – every node has at most two children, which distinguishes a binary tree from a general tree.

What is a binary tree?

A binary tree is a hierarchical data structure made of nodes. Each node holds a value and has at most two children, referred to as the left child and the right child. There is exactly one node at the top called the root. Nodes with no children are called leaves. The longest path from the root down to any leaf defines the height of the tree.

The defining rule is simply that the branching factor is limited to two. This constraint is what makes binary trees the foundation for binary search trees, heaps, expression trees, and Huffman coding trees.

package com.bank.model;

import java.math.BigDecimal;

public class AccountNode {
    BigDecimal balance;
    AccountNode left;
    AccountNode right;

    public AccountNode(BigDecimal balance) {
        this.balance = balance;
        this.left = null;
        this.right = null;
    }
}

Why do we need binary trees?

Binary trees exist because many real-world relationships are hierarchical and binary branching provides a good balance between simplicity and efficiency. A linked list is linear and gives O(n) search. A hash map gives O(1) average lookup but no ordering. A binary tree, when balanced, gives O(log n) search, insertion, and deletion while maintaining sorted order.

In banking, trees model approval hierarchies, decision engines for loan eligibility, and index structures for fast account lookups.

// Why not a linked list? Search is O(n)
// Why not a hash map? No ordering, no range queries
// Binary tree (balanced): O(log n) search with ordering preserved

What are the key terms?

The vocabulary of binary trees appears in every interview and must be precise.

• Parent – a node that has at least one child.
• Child – a node directly below a parent.
• Sibling – two nodes that share the same parent.
• Depth – the number of edges from the root to a node. The root has depth 0.
• Height – the number of edges from a node to its deepest descendant leaf. A leaf has height 0.
• Subtree – the tree rooted at any node, including all its descendants.

// Building a small hierarchy tree
AccountNode root = new AccountNode(new BigDecimal("1000000")); // Branch Manager
root.left = new AccountNode(new BigDecimal("500000"));         // Left Deputy
root.right = new AccountNode(new BigDecimal("500000"));        // Right Deputy
root.left.left = new AccountNode(new BigDecimal("100000"));    // Officer (leaf)
// Depth of officer: 2, Height of tree: 2

How do you traverse a binary tree?

Traversal means visiting every node exactly once. There are four standard traversals.

Inorder (Left, Node, Right) visits the left subtree, then the node, then the right subtree. On a BST this produces sorted output. Preorder (Node, Left, Right) visits the node first, useful for cloning. Postorder (Left, Right, Node) visits the node last, useful for deletion. Level-order visits nodes level by level using a queue.

package com.bank.service;

import com.bank.model.AccountNode;
import java.util.LinkedList;
import java.util.Queue;

public class TreeTraversalService {

    public static void inorder(AccountNode node) {
        if (node == null) return;
        inorder(node.left);
        System.out.println("Balance: " + node.balance);
        inorder(node.right);
    }

    public static void preorder(AccountNode node) {
        if (node == null) return;
        System.out.println("Balance: " + node.balance);
        preorder(node.left);
        preorder(node.right);
    }

    public static void levelOrder(AccountNode root) {
        if (root == null) return;
        Queue<AccountNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            AccountNode node = queue.poll();
            System.out.println("Balance: " + node.balance);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
}

How is a binary tree different from a BST and a heap?

| Aspect | Binary Tree | Binary Search Tree | Heap |
|---|---|---|---|
| Ordering | None | Left < Node < Right | Parent > Children (max-heap) |
| Search | O(n) linear | O(log n) balanced | O(n) for arbitrary |
| Best for | General hierarchy | Sorted data, range queries | Priority queue, min/max |
| Balancing | Not required | AVL/Red-Black for O(log n) | Shape maintained by array |

A plain binary tree has no ordering rule, so searching it requires visiting every node. The power comes from adding rules: a BST enforces left < node < right for logarithmic search, and a heap enforces parent-child ordering for fast min/max access.

// Plain binary tree: must check every node
public static boolean contains(AccountNode node, BigDecimal target) {
    if (node == null) return false;
    if (node.balance.compareTo(target) == 0) return true;
    return contains(node.left, target) || contains(node.right, target);
}
// Time: O(n) because no ordering to guide the search

What are the types of binary trees?

Several special forms of binary trees appear in interviews.

• Full binary tree – every node has either 0 or 2 children, never just one.
• Complete binary tree – all levels are fully filled except possibly the last, which is filled from left to right. Heaps use this shape.
• Perfect binary tree – all internal nodes have two children and all leaves are at the same level. A perfect tree of height h has 2^(h+1) - 1 nodes.
• Balanced binary tree – the heights of left and right subtrees differ by at most 1 at every node. AVL trees enforce this.
• Degenerate (skewed) tree – every node has only one child, effectively a linked list.

// Perfect binary tree of height 2: 7 nodes
//        1
//       / \
//      2   3
//     / \ / \
//    4  5 6  7
// Nodes = 2^3 - 1 = 7

What are common mistakes with binary trees?

The most common mistake is confusing depth and height.

// WRONG: "height of the root is 0"
// Height of the root is the height of the tree (longest path to leaf)
// Depth of the root is 0 (distance from root to root)

// CORRECT:
// depth(node) = number of edges from root to node
// height(node) = number of edges from node to deepest leaf
// height(root) = height of tree
// depth(root) = 0

Another mistake is forgetting null checks in recursive traversals, causing NullPointerException.

What is the time complexity of common operations?

For a plain binary tree with n nodes:

• Search – O(n), no ordering to guide the search.
• Insertion – O(1) if inserting at a known position, O(n) to find a position.
• Deletion – O(n) to find the node, O(1) to remove it.
• Traversal – O(n) for any traversal (every node visited once).
• Height computation – O(n), must visit every node.

For a balanced BST, search, insert, and delete drop to O(log n).

public static int height(AccountNode node) {
    if (node == null) return -1; // height of empty tree is -1
    return 1 + Math.max(height(node.left), height(node.right));
}
// Time: O(n), visits every node

What should a senior engineer know?

A senior engineer should know that the shape of a binary tree determines its performance. A balanced tree gives O(log n) operations, while a degenerate tree degrades to O(n). This is why self-balancing trees (AVL, Red-Black) exist in production systems.

They should also know the recursive structure: every binary tree is either empty (null) or a node with two binary-tree children. This recursive definition is the foundation of every recursive tree algorithm.