A.1.6: Trees
- 1.Trees are collections of nodes connected by uni-directional edges without cycles
- 2.Trees store hierarchical data and are commonly used for applications such as file systems, nested UI representation, search and language processing
- 3.Binary trees and binary search trees are the most common trees in algorithm problems
- 4.There are 2 common tree traversal algorithms: depth-first search (DFS) and breadth-first search (BFS)
- 5.Within DFS there are 3 orders of traversing nodes: pre-order, in-order and post-order
Simple whiteboard introduction to trees
Sample computer science tree. The node outlined in red is the root node. Source: Wikipedia
Trees are collections of nodes connected by uni-directional edges with no cycles. They are typically drawn from top to bottom as in the image above. For any 2 connected nodes, the source node is called the "parent" and the target node is called the "child". Nodes with no children are called "leaf" nodes. Each node typically has a payload, which is often a number in algorithm problems but can be anything in practical problems, such as folder names or React components.
Trees store hierarchical data and are commonly used for application such as file systems (think the folder structure in terminal), nested UI representation (think React component hierarchy), search (think dictionary or encyclopaedia search), and language processing (imagine a tree representing common word orders). They are not uncommon algorithm problems, which is why we are learning them now.
The following tree node definition is for binary trees, the most common kind of tree we will encounter in algorithm problems. Binary trees have at at most 2 children per parent, and we generally refer to the children as left and right nodes.
// Binary tree node definition
class Node {
constructor(val) {
// The node value is stored in an attribute called val
this.val = val;
// Initialise left and right child nodes to null
this.left = null;
this.right = null;
}
}
// Initialise a binary tree and populate its nodes
const root = new Node(3);
root.left = new Node(1);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(3);
// The resulting tree should look like the following
// 3
// / \
// 1 2
// / \ / \
// 3 4 5 3
Sample binary search tree. Source: Wikipedia
Binary search trees (BSTs) are binary trees where every node has the following properties:
- 1.All nodes in the left subtree (subtree that extends from the parent node's left child) have values smaller than the parent node
- 2.All nodes in the right subtree (subtree that extends from the parent node's right child) have values larger than the parent node
These properties are especially useful for search algorithms, because given relatively "balanced" (all subtrees have the same depth) BSTs, we will be able to search for elements in BSTs in
O(log(n)) time. BSTs can be considered a visual representation of binary search.// BST node definition
class Node {
constructor(val) {
self.value = val;
self.left = null;
self.right = null;
}
}
// Creating a BST
const root = new Node(5);
root.left = new Node(3);
root.right = new Node(8);
root.right.left = new Node(7);
// The resulting tree should look like the following
// 5
// / \
// 3 8
// /
// 7
The following tree node definition is for a generic tree with no limit to the number of child nodes per parent. These are less common but occasionally seen in algorithm problems.
// Generic tree node definition
class Node {
constructor(val) {
// The node value is stored in an attribute called val
this.val = val;
// Store children in array, starting with empty array when no children
this.children = [];
}
}
Most tree algorithm problems involve traversing (i.e. going through) the nodes in a tree and calculating a result, for example summing the value of nodes, finding a specific value in the tree, or determining if a tree is balanced (equal nodes on left and right).
There are 2 common forms of tree traversal: depth-first search (DFS) and breadth-first search (BFS). DFS means traversing down every path until we reach a leaf node before exploring other paths. BFS means traversing all nodes at each level of depth (distance from root node) before proceeding to the next level of depth. DFS is simpler and more common. BFS is more specialised for certain kinds of problems such as finding the shortest path in a tree.
Overview of BFS, DFS and the 3 permutations of DFS
DFS is the default form of tree traversal and we typically implement DFS with recursion.
Illustration of DFS. Source: Viva Differences
The following code uses DFS to find value
x in a tree. The algorithm returns true if x exists in the tree and false if not.// The initial call to findXInTree passes in the root node
const findXInTree = (node, x) => {
// If recursion reaches child of leaf node, x was not found
if (!node) {
return false;
}
// If current node has value x, x is found
if (node.val === x) {
return true;
}
// Return true if x is in the left or right subtrees of node, false otherwise
return findXInTree(node.left, x) || findXInTree(node.right, x);
}
Notice the algorithm looks like many of the recursive algorithms we have written before, with base cases and recurrence relations. DFS algorithms typically examine the current node in the base cases and pass child nodes to the recursive functions in recurrence relations.
The above algorithm has a time complexity of
O(n), where n is the number of nodes in the tree. This is because the algorithm will need to visit at most all nodes in the tree to find x. This algorithm has a space complexity of O(1) because it does not allocate any additional memory beyond what is provided.Certain DFS problems are better solved if we can manipulate the order in which we traverse nodes. The following 3 traversals are variants of DFS that determine the order in which we traverse left child, parent, and right child nodes. All 3 traversals assume we are traversing a binary tree.
Pre-Order Traversal implies visiting nodes in the following order. This is helpful in situations such as searching a binary search tree, because we will need to inspect the parent first to determine whether the value we are looking for is in the left or right subtree.
- 1.Parent
- 2.Left Child
- 3.Right Child
const preOrderTraversal = (node) => {
// 1) Check parent
if (node.val) {
// Return something
return;
}
// 2) Check left child
preOrderTraversal(node.left);
// 3) Check right child
preOrderTraversal(node.right);
}
In-Order Traversal implies visiting nodes in the following order. This is helpful in situations such as printing the values in a binary search tree in ascending order.
- 1.Left Child
- 2.Parent
- 3.Right Child
const inOrderTraversal = (node) => {
// 1) Check left child
inOrderTraversal(node.left);
// 2) Check parent
if (node.val) {
// Return something
return;
}
// 3) Check right child
inOrderTraversal(node.right);
}
Post-Order Traversal implies visiting nodes in the following order. This is helpful in situations where we might want to operate on all leaf nodes before their parents, for example when deleting nodes in a tree.
- 1.Left Child
- 2.Right Child
- 3.Parent
const postOrderTraversal = (node) => {
// 1) Check left child
postOrderTraversal(node.left);
// 2) Check right child
postOrderTraversal(node.right);
// 3) Check parent
if (node.val) {
// Return something
return;
}
}
Illustration of DFS. Source: Viva Differences
The following algorithm returns all values in the tree level by level from top to bottom. This is hard to do with DFS because DFS explores each subtree completely before moving on to the next. BFS traverses nodes in exactly the order we want, making it easy to add their values to a list in level order.
BFS is typically implemented using queues. Since there is no built-in queue data structure in JavaScript, we use arrays instead, with the array
shift method to dequeue elements from the front of the array. Note that shift is a relatively inefficient O(n) operation, and when we need more efficient algorithms we would either use linked lists to implement a queue data structure, or use Python and its built-in deque data structure (uses linked lists underneath) for queue operations.The BFS algorithm works by iteratively (no recursion) adding each node's children to a queue, and visiting nodes in the order they appear in the queue. This guarantees all nodes at each level will be visited before nodes at lower levels. See above video for a visual description.
// Return list of values in tree in level order from top to bottom
const levelOrder = (root) => {
const levelOrderValues = [];
// Store upcoming nodes in a queue
q = [root];
while (q.length > 0) {
// Iteratively dequeue first node in queue until queue is empty
currNode = q.shift();
// Perform operation on curr node, in this case add to level order values
levelOrderValues.push(currNode.val);
// Enqueue left child if any
if (currNode.left) {
q.push(currNode.left);
}
// Enqueue right child if any
if (currNode.right) {
q.push(currNode.right);
}
}
return levelOrderValues;
};
In each loop, we enqueue the left and right child (assuming binary trees) of the current node to our queue, if any. The algorithm starts with only the root node in the queue, and ends when the queue is empty. BFS also works for non-binary trees, where we would enqueue all children and not just left and right children.
The above algorithm has a time complexity of
O(n), where n is the number of nodes in the tree. This is because the algorithm will need to visit at most all nodes in the tree to find x. This algorithm has a space complexity of O(n) because levelOrderValues has size n when it is returned.- 1.
- 2.
The following exercises are sorted in increasing order of difficulty, and organised to help us keep track of milestones. Please do as many as you can during Bootcamp and feel free to complete the rest at a later time.
These starter problems cover basic tree traversal which will be helpful for the LeetCode and HackerRank exercises to follow.
Please fork starter code Repls and attempt solutions there. Feel free to compare with reference solutions after attempting each problem. Have fun!
- 1.
- 2.
Binary tree traversal.
- 1.
- 2.
- 1.
- 3.
- 1.
Binary Search Trees (BST).
- 1.Binary Search Tree Insertion (HackerRank) you will need to define a node as well as additional code to insert into the Binary Tree.
- 2.
- 3.
- 1.Hint: Consider in-order traversal to traverse a binary search tree in increasing order
- 4.
DFS pre-order, in-order and post-order traversal.
See Pre-Order, In-Order, and Post-Order section above for a recap on the various DFS traversal orderings. For non-binary trees that can have more than 2 children, when we iterate through an array of children we are typically iterating from left to right children.
- 1.
- 2.
- 3.
BFS.
- 1.
- 2.
- 1.Hint: Consider BFS for efficiency
- 3.
- 1.Hint: Both DFS and BFS should work, DFS will be simpler
- 2.Can you think of both DFS and BFS solutions?
- 3.
Misc tree problems.
- 1.
- 1.
- 2.
- 2.
Misc tree problems.
- 1.
- 2.
- 1.
- 2.
Misc tree problems.
- 1.
- 2.
- 3.
- 4.
- 1.Hint: Consider starting in the middle of the array and using recursion.
- 5.
- 1.Hints
- 1.Each time we reach a leaf node, we've explored a valid path.
- 2.How can we keep track of the path up to each leaf node such that when we reach a leaf node in our recursion, we can add that path to the list of valid paths? Do we need an additional input parameter to our recursive function, i.e. a recursive helper function for this?
- 3.Where can we store our list of valid paths? Should it be inside or outside of our recursive helper function?
- 2.FTBC3 class video discussion on algorithm and how to write helper function for recursion problems to pass additional parameter to recursive children
- 3.
- 6.
- 1.Hint: BFS
- 7.
- 1.Hint: The minimum absolute distance in a tree with root node
rootis the minimum of the following 4 values.- 1.
minAbsDist(root.left) - 2.
minAbsDist(root.right) - 3.
abs(root.val - maxValInLeftSubtree) - 4.
abs(root.val - minValInRightSubtree))
- 8.
- 1.
- 2.
- 9.
- 1.
- 2.
- 10.
- 11.
- 12.
Last modified 5mo ago