# A.1.6: Trees

## Learning Objectives

Trees are collections of nodes connected by uni-directional edges without cycles

Trees store hierarchical data and are commonly used for applications such as file systems, nested UI representation, search and language processing

Binary trees and binary search trees are the most common trees in algorithm problems

There are 2 common tree traversal algorithms: depth-first search (DFS) and breadth-first search (BFS)

Within DFS there are 3 orders of traversing nodes: pre-order, in-order and post-order

## Introduction

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.

## Tree Types and Initialisation Code

### Binary Tree

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 Search Tree

Binary search trees (BSTs) are binary trees where every node has the following properties:

All nodes in the left subtree (subtree that extends from the parent node's left child) have values smaller than the parent node

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.

### Generic Tree

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.

## Tree Traversal

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.

## Depth-First Search (DFS)

DFS is the default form of tree traversal and we typically implement DFS with recursion.

### Example: Find `x`

in tree

`x`

in tree#### Algorithm description

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.

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.

#### Time and space complexity

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.

### Pre-Order, In-Order and Post-Order Traversal

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**

**Pre-Order Traversal**

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.

Parent

Left Child

Right Child

#### In-Order Traversal

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.

Left Child

Parent

Right Child

#### Post-Order Traversal

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.

Left Child

Right Child

Parent

## Breadth-First Search (BFS)

### Example: Return tree values in level order

#### Algorithm description

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.

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.

#### Time and space complexity

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.

## Additional Resources

Read pages 111-114 (book pages 100-103) in the Cracking the Coding Interview PDF

FTBC3's class video when we introduced trees

## Exercises

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.

### Pre-Class

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!

FTBC3 class video where we solved the 1st 2 problems together (Python)

### Part 1

Binary tree traversal.

Univalued Binary Tree (LeetCode)

Height / Maximum Depth of a Binary Tree (HackerRank, LeetCode)

FTBC3 class video discussion on solution and how to trace code in a recursion problem

Maximum Depth of N-ary Tree (LeetCode)

Hint: Review Maximum Depth of Binary Tree problem before attempting this one

### Part 2

Binary Search Trees (BST).

See Binary Search Tree section above for recap on properties of BSTs.

Binary Search Tree Insertion (HackerRank) you will need to define a node as well as additional code to insert into the Binary Tree.

Search in a Binary Search Tree (LeetCode)

Increasing Order Search Tree (LeetCode)

Hint: Consider in-order traversal to traverse a binary search tree in increasing order

Lowest Common Ancestor of a Binary Search Tree (HackerRank, LeetCode)

### Part 3

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.

Pre-Order Traversal (HackerRank, LeetCode)

In-Order Traversal (HackerRank)

Post-Order Traversal (HackerRank, LeetCode)

### Part 4

BFS.

Level-Order Traversal (HackerRank)

Minimum Depth of Binary Tree (LeetCode)

Hint: Consider BFS for efficiency

Same Tree (LeetCode)

Hint: Both DFS and BFS should work, DFS will be simpler

Can you think of both DFS and BFS solutions?

FTBC3 class video discussion on solution and runtime

### Part 5

Misc tree problems.

Path Sum (LeetCode)

Rocket solution code (Python)

FTBC3 class video solution (Python)

Balanced Binary Tree (LeetCode)

### Part 6

Misc tree problems.

Two Sum IV Input is a BST (LeetCode)

Range Sum of BST (LeetCode)

Rocket solution code (Python, naive solution without pruning)

FTBC3 class video solution (Python)

### Part 7

Misc tree problems.

### More Comfortable

Leaf-Similar Trees (LeetCode)

Sum of Left Leaves (LeetCode)

Subtree of Another Tree (LeetCode)

Convert Sorted Array to Binary Search Tree (LeetCode)

Hint: Consider starting in the middle of the array and using recursion.

Binary Tree Paths (LeetCode)

Hints

Each time we reach a leaf node, we've explored a valid path.

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?

Where can we store our list of valid paths? Should it be inside or outside of our recursive helper function?

FTBC3 class video discussion on algorithm and how to write helper function for recursion problems to pass additional parameter to recursive children

LeetCode reference solution from LeetCode Discuss tab

Average of Levels in Binary Tree (LeetCode)

Hint: BFS

Minimum Absolute Difference in BST (LeetCode)

Hint: The minimum absolute distance in a tree with root node

`root`

is the minimum of the following 4 values.`minAbsDist(root.left)`

`minAbsDist(root.right)`

`abs(root.val - maxValInLeftSubtree)`

`abs(root.val - minValInRightSubtree))`

Symmetric Tree (LeetCode)

Rocket solution code (Python)

FTBC3 class video solution (Python)

Cousins in Binary Tree (LeetCode)

Rocket Academy solution code (Python)

Rocket Academy video solution (Python)

Diameter of Binary Tree (LeetCode)

Binary Tree Right Side View (LeetCode) (Medium)

Binary Tree Zigzag Level Order Traversal (LeetCode) (Medium)

Last updated