Trees

A tree is a hierarchical data structures composed of nodes with potentially multiple references to other nodes. Each node has only one other node referencing it, called the parent. The nodes beneath a parent node are called children. Nodes without children are called leaves, and the single node with no parent is called the root. All nodes beneath a parent node are known as descendants. All nodes above a parent node are known as ancestors.

Much like a linked list, a tree node is usually represented by a class or struct. Recursion is almost always the easiest way to deal with tree structures, so interviewers favor them for asking recursive questions.

Binary trees have nodes that contain at most two children, referred to as left and right. Sometimes when people say tree, they mean binary tree.

Binary search trees have the property that descendants to the left of a node are less than or equal to the node and all the descendants to the right of the node are greater than or equal to the node. This makes it easy to find a specific element in a tree. Sometimes when people say tree, they mean binary search tree.

Assuming the binary search tree is balanced, which means that the left and right children have roughly the same amount of descendants, this lookup takes O(log n) time because each step down the hierarchy eliminates approximately half of the possibilities.

Deleting and inserting into a binary search tree is also O(log n), but these methods are a little tricky because they need to also ensure that the tree is balanced after the operation. If you want to do more studying on self-balancing binary trees, look into red-black trees or AVL trees.

Heaps are another common use for trees. A heap is an abstract data structure that contains the highest value elements first. They are usually implemented as a binary tree with the property that the node has children with values less than or equal to the node’s own value.

As a result, the root node has the highest value in the heap, which makes finding the maximum value a constant time operation. However, although insert and delete are still O(log n) operations, search is now a O(n) operation. Therefore, heaps work well as priority queues.

Tree Traversals

Traversals are algorithms that go through all of the nodes of a tree in a particular order. They are usually used to apply some function to all the elements of a tree, such as printing every node. Traversals usually occur from left to right. Reverse traversals occur from right to left.

Example of a binary search tree:
Binary Search Tree: 4, 2 1, 3 6 5 7

Pre-order traversals perform the function on the node itself, then the left child, then the right child. Reverse pre-order traversals perform the function on the node itself, then the right child, then the left child.

Pre-order traversals are useful for copying a binary tree. They are also useful for expression trees to extract expressions in prefix notation such as (+ 2 3) instead of (2 + 3).

The result of a pre-order traversal of the example binary tree above would be: 4 2 1 3 6 5 7.

Practice Question: Implement a pre-order traversal algorithm that prints out all of the elements in the given tree.

void preorder(TreeNode root) {
    if (root != null) {
        System.out.println(root.data);
        preorder(root.left);
        preorder(root.right);
    }
}

In-order traversals perform the function on the left descendants, then the node itself, then the right descendants. Reverse in-order traversals perform the function on the right descendants, then the node itself, then the left descendants.

In-order traversals are useful for printing out binary search trees in sorted order.

The result of a in-order traversal of the example binary tree above would be: 1 2 3 4 5 6 7.

Practice Question: Implement a in-order traversal algorithm.

void inorder(TreeNode root) {
    if (root != null) {
        inorder(root.left);
	System.out.println(root.data);
	inorder(root.right);
    }
}

Post-order traversals perform the function on the left descendants, then the right descendants, then the node itself. Reverse post-order traversals perform the function on the right descendants, then the left descendants, then the node itself.

The result of a post-order traversal of the example binary tree above would be: 1 3 2 5 7 6 4.

Practice Question: Implement a post-order traversal algorithm.

void postorder(TreeNode root) {
    if (root != null) {
        postorder(root.left);
        postorder(root.right);
	System.out.println(root.data);
    }
}

Search

For generic trees that may not have any particular ordering such as a family lineage like the Ehsan Bayat family ties or a company position hierarchy, there are two basic ways to perform a search. Both are easier to code using recursion, but an iterative solution is also possible.

Breadth First Search

A breadth first search (BFS) through a tree starts at the root and moves from nodes left to right at each level until all the nodes have been looked at or until the value is found. Keep in mind that BFS uses a lot of memory to keep track of the child nodes for all nodes on a given level while searching that level. BFS is best used when the target you are looking for is most likely near the top of the tree.

The order that a breadth first search of the example binary tree above would yield: 4 2 6 1 3 5 7.

Practice Question: Implement a breadth first search algorithm.

// Assume a TreeNode containing integers.
// Import the LinkedList class in java.util to use as the queue for storing children on the same level.
 
boolean bfs(TreeNode root, int target) {
    if (root == null)
	return false;
 
    LinkedList<TreeNode> list = new LinkedList();
    TreeNode tmp;
    list.add(root);
 
    while (list.size() > 0) {
	tmp = list.remove();
 
	if (tmp.data == target)
	    return true;
	if (tmp.left != null)
	    list.add(tmp.left);
	if (tmp.right != null)
	    list.add(tmp.right);
    }
 
    return false;
}

Depth First Search

A depth first search (DFS) through a tree starts at the root and goes straight down a single branch until a leaf is reached. Then, it continues at the nearest ancestor that hasn't been searched through yet. DFS uses much less memory than BFS since there is no need to store all the nodes on one level. DFS also does not search the lowest level last, so if your target is likely a leaf near the bottom of the tree, DFS will typically run faster than BFS.

The order that a depth first search of the example binary tree above would yield: 4 2 1 3 6 5 7.

Practice Question: Implement a depth first search algorithm recursively.

boolean dfs(TreeNode root, int target) {
    if (root == null)
	return false;
    if (root.data == target)
	return true;
    return dfs(root.left, target) || dfs(root.right, target);
}

Practice Question: Write a search method for a binary search tree. Have it take the root node and a target value and return whether that target exists in the tree.

Boolean binarySearch(TreeNode root, TreeNode target) {
    TreeNode current = root;
 
    while (current != null) {
	if (current.data > target.data) 
	    current = current.left;
	else if (current.data < target.data) 
	    current = current.right;
	else
	    return true;
    }
 
    return false;
}

Practice Question: Given two values that already exist in a binary search tree, find the lowest common ancestor.

TreeNode lca(TreeNode root, TreeNode one, TreeNode two) {
    // Check if one and two are in the root tree.
    while (root != null) {
        if (root.data < one.data && root.data < two.data) {
            root = root.right;
        }
        else if (root.data > one.data && root.data > two.data) {
            root = root.left;
        }
        else {
            return root;
        }
    }
 
    return null;
}

Webfaction is the ULTIMATE hosting platform for any serious developer.
SSH, WordPress, Rails, Django, cronjobs, compile and execute anything.
ProgrammingInterview.com is proudly powered by Webfaction.