Binary Trees Boot Camp

Bootcamp Trees

A Binary Tree is a data structure in which each node has a value, a pointer to a left child node and a pointer to a right child node.

If you are given a tree problem make sure to clarify immediately the properties of the given tree: are you given a BST (Binary Search Tree), a simple BT or another type of tree? Do nodes have pointers to their parent?

Here are common definitions that will help you reason about the problem with your interviewer and disambiguate requirements.

Balanced binary tree: height of the tree is O(logn). AVL trees maintain the property that the difference between the height of the left subtree and the height of the right subtree is 1.

Full Binary tree: every node has 0 or 2 children.

Complete trees: all levels are completely filled except for possibly the last one and the last level is filled from left to right (Heap is an example of a complete tree).

Perfect tree: all internal nodes have 2 children and all leaves are at the last level

Heap (max): a complete binary tree where each node has a value higher than its children.

Tree traversal

Most tree questions will require some sort of tree traversal to be solved. A tree can be traversed in two ways: DFS (Depth First Search) and BFS (Breadth First Search).

Depth-first Search (DFS)

void dfs(BTNode node) {
    if (node == null) {
        return;
    }

    dfs(node.left);
    System.out.println(node.data);
    dfs(node.right);
}

DFS can be performed in three different ways:

  1. in-order traversal: left-root-right
  2. pre-order traversal: root-left-right
  3. post-order traversal: left-right-root

Breadth-first Search (BFS)

void bfs(BTNode root) {
    Deque<BTNode> queue = new LinkedList<BTNode>();
    queue.add(root);

    while(!queue.isEmpty()) {
        BTNode node = queue.remove();
        System.out.println(node.data);

        if (node.left != null)
            queue.add(node.left);

        if (node.right != null)
            queue.add(node.right);
    }
}

Things to consider when choosing DFS vs BFS

  • DFS is a recursive algorithm, so keep in mind the extra space needed for the call stack when analyzing space complexity. The maximum size of the stack is O(h) where h is the maximum height of the tree which is n for unbalanced trees and logn for balanced tree.

  • BFS uses a queue and the size of the queue at any given time is the number of nodes at any given level which is at its maximum at the last level in a perfect binary tree. So space complexity in the worst case scenario is O(2^h) for a perfect binary tree.

Back to homepage