Binary Trees

Introduction

There is a lot to cover on this one so I'll add a table of contents for the sections. The goal is to build up an understanding of the basic binary tree structure and common algorithms. Structures will be class-based, and I'll introduce many functional techniques such as the various traversal algorithms. With trees, there are iterative and recursive approaches. While this is largely preferential, some techniques require iterative and some feel more intuitive recursively. I will include both where either are reasonable options.

Sections

• The Basics
  • What Trees Are
• Traversals
  • Pre-order Traversal (DFS)
  • In-order Traversal (DFS)
  • Post-order traversal (DFS)
  • Level-order Traversal (BFS)
• Operations
  • Getting the Tree's Height
  • Searching for Values
  • Adding Nodes
  • Removing Nodes by Value
  • The Full Binary Tree Class

The Basics

What Trees Are

Trees are directed graphs without cycles that are connected such that every node can be reached from a single root node. There can only be a single root, and child nodes can only have one parent. The purpose of this article is to dive deep on binary trees, but trees can be n-ary meaning that a node can have an unlimited number of children (n children).

Binary trees are more specific in that each node can have two child nodes at most. In theory, every node could have any type of value, but it is more common for the values to be of the same type. With this constraint, the class for a BinaryTreeNode of a binary tree is represented as:

class BinaryTreeNode<T> {
  val: T | undefined
  left: BinaryTreeNode<T> | null
  right: BinaryTreeNode<T> | null
  constructor(val?: T, left?: BinaryTreeNode<T> | null, right?: BinaryTreeNode<T> | null) {
    this.val = val ?? undefined
    this.left = left ?? null
    this.right = right ?? null
  }
}

Along with val for value, each node has left and right pointers that point to other nodes. Again, I will cover this in a future article perhaps, but if this were an n-ary tree node, left and right would be replaced with an array of nodes that is usually named children. Before moving on, here is a visual representing a binary tree's shape:

     1
   /   \
  2     3
 / \   / \
4   5 6   7

When most people see trees, they immediately resemble recursion which is why working with trees can be a very natural way to learn recursion. Popular problems like Fibonacci or building strings of valid parentheses recursively call things in a shape that highly resembles a binary tree's structure. Given this, most algorithms related to trees can be done through recursion, and I actually solved many problems on LeetCode without formally learning any traversal algorithms just by knowing recursion beforehand. That being said, let's dig into the basic traversals.

Traversals

A traversal is the method or order of which to move through and process nodes of the tree. Of these, there are two broad categories: Depth-first search (DFS) and Breadth-first search (BFS). Starting out I'll cover DFS orders such as pre-order, in-order, and post-order. Then, I'll touch on BFS which is the level-order traversal.

For all examples, I'll reference the following binary tree:

     1
   /   \
  2     3
 / \   / \
4   5 6   7

Pre-order Traversal (DFS)

Pre-order traversal is a depth first search technique that prioritizes a path to dive through before moving to the next. For binary trees, this would look like exploring the left most path before visiting any right paths. Using the tree above, a pre-order path would visit each value in this order: [1, 2, 4, 5, 3, 6, 7]. Algorithmically, it processes the current node, then recurse left, then recurse right. We make this same current-left-right decision at every parent node we visit. If the parent has no children, then the recursion ends.

function preOrderRecursive(node: BinaryTreeNode | null) {
  if (!node) return
  console.log(node.val) // Process current value somehow
  if (node.left) preOrderRecursive(node.left)
  if (node.right) preOrderRecursive(node.right)
}

With recursion, it is fairly easy to visualize moving through the tree. Iteratively, it can be more difficult to understand at first. Recursion is essentially just a stack of function calls (the call stack), so by using a stack that keeps the next element to process at the top, we can achieve the same result. Performance-wise, these approaches are roughly the same, but the size of the stack can be directly controlled if an explicit stack is used which is not possible in the recursive approach. This will also eliminate the risk of stack overflow errors.

However, the order of operations is more difficult to understand. For recursion, we simply did current-left-right. Iteratively, left most values need to be at the top of the stack so right values are pushed to the stack first which feels backwards:

function preOrderIterative(node: BinaryTreeNode | null) {
  if (!node) return

  let stack = [node]

  while (stack.length > 0) {
    const curr = stack.pop()!

    console.log(curr.val) // Process current value somehow

    if (curr.right) stack.push(curr.right)
    if (curr.left) stack.push(curr.left)
  }
}

For a visual aid, here is what the stack is doing over the first 3 iterations:

1. stack = [1]
2. stack = [3, 2] -> 3 added first then 2, so 2 is popped first
3. stack = [3, 5, 4] -> Left values get stored on top to be processed first

In-order Traversal (DFS)

Recursively, this ordering is just a slight variation on pre-order. Instead of processing current first, we would process left, then the current node, then the right. Using the example tree, the idea would be to process nodes as they appear from left to right: [4, 2, 5, 1, 6, 3, 7]. This method will become useful for Binary Search Trees - a special binary tree with an in-order traversal that is in ascending/increasing order. More on that later. For now, here is the recursive left-current-right method. Notice how similar it is to pre-order:

function inOrderRecursive(node: BinaryTreeNode | null) {
  if (!node) return
  if (node.left) inOrderRecursive(node.left)
  console.log(node.val) // Process current value somehow
  if (node.right) inOrderRecursive(node.right)
}

Iteratively, this traversal is probably the most difficult. A stack is still required for backtracking, but given that the left-most node is processed first, current must be moved as left as it can be moved whenever possible. At every parent node, the left node or subtree should be fully processed before checking anything to the right. To accomplish that, a nested while loop is needed to move as left as possible. After the first iteration, this will only run after processing a node that has a right child. If so, we move to this right child node, push it immediately, and process its entire left-subtree before processing the right child itself.

function inOrderIterative(node: BinaryTreeNode | null) {
  if (!node) return

  let stack: BinaryTreeNode[] = []

  while (stack.length > 0 || node) {
    while (node) {
      stack.push(node)
      node = node.left
    }

    node = stack.pop()!

    console.log(node.val)

    node = node.right
  }
}

This one has a few edgy pieces of logic that make it trickier to understand. Just remember the goal is left-current-right! At a given parent, the current pointer is moved as far left as possible, pushing left nodes onto the stack along the way. Once it hits null, the left-most value is at the top of the stack and is popped off and processed first. It then checks if that node (treating it as current) has any right children by setting node to node.right. If that node exists, it will be pushed to the top of the stack at the beginning of the next iteration as well as all of its left-most nodes, if any. One way to block this in the left-current-right mindset, is that left is handled by the while loop, current is processed in the middle when being popped, and right is handled at the bottom (it is really processed later, but the last line of each loop sets that up).

Here is a dry run example and pay close attention to the processing order (the order of the numbers being popped):

1. • stack -> [1, 2, 4]
     • 4 is popped and processed
     • it has no right child, so node ends as null
2. • stack -> [1, 2] (nested while loop doesn't run because node is null)
     • 2 is popped and processed
     • 2 has a right child, so node ends as 5
3. • stack -> [1, 5] (nested while loop runs to push 5, but only once since 5 has no left children)
     • 5 is popped and processed
     • 5 has no right child, so node ends as null

Post-order traversal (DFS)

This ordering looks to process nodes as left-right-current. Basically, child nodes (or entire subtrees) are processed before the parent. Post-order would process the example tree as [4, 5, 2, 6, 7, 3, 1]. Once again, the recursive version is just a small change in the line order:

function postOrderRecursive(node: BinaryTreeNode | null) {
  if (!node) return
  if (node.left) postOrderRecursive(node.left)
  if (node.right) postOrderRecursive(node.right)
  console.log(node.val) // Process current value somehow
}

This is the first example of an iterative solution where I think it is unlikely to need to know this, but I'll include it anyway. It feels a little messy because two stacks are required to handle this ordering. The first stack is used with the first loop to handle a standard pre-order traversal, and the processing of that traversal is to push values to the second stack which will result in the values being in a pre-order sequence. It needs to be reversed so that values are popped in post-order in the second while loop.

function postOrderIterative(root: BinaryTreeNode | null) {
  if (!root) return

  let preOrderStack = [root]
  let postOrderStack: BinaryTreeNode[] = []

  while (preOrderStack.length > 0) {
    const curr = preOrderStack.pop()!

    postOrderStack.push(curr) // Process current value somehow

    if (curr.left) preOrderStack.push(curr.left)
    if (curr.right) preOrderStack.push(curr.right)
  }

  while (postOrderStack.length > 0) {
    const curr = postOrderStack.pop()!
    console.log(curr.val)
  }
}

Level-order Traversal (BFS)

Until now, all of the traversal algorithms have taken a depth-first approach meaning they dive as deep down one path as possible. In a level-order traversal, nodes are processed by level, usually from left to right. This means after processing the parent, both children must be processed before going deeper. Instead of depth, it is a wider search around the current node, or breadth-ier search. For the example tree, the level order will process as [1, 2, 3, 4, 5, 6, 7].

For this one, only the iterative approach is important to learn:

function levelOrderIterative(root: BinaryTreeNode | null) {
  if (!root) return

  let queue = [root]

  while (queue.length > 0) {
    const curr = queue.shift()!

    console.log(curr.val)

    if (curr.left) queue.push(curr.left)
    if (curr.right) queue.push(curr.right)
  }
}

For this, values are enqueued (pushed) in level order and dequeued (shifted) on each iteration. Note that this algorithm can be more efficient if the underlying structure is a linked list instead of an array because shifting is slower.

Additionally, I think a useful technique to cover while on level-order is how to process each level as a group. This moves into applications a bit, but the pattern is important. By groups, I mean we may want to process nodes as [[1], [2, 3], [4, 5, 6, 7]].

function levelOrderGroups(root: BinaryTreeNode | null) {
  if (!root) return

  let queue = [root]

  while (queue.length > 0) {
    let group = []
    let m = queue.length

    for (let i = 0; i < m; i++) {
      let curr = queue.shift()!

      group.push(curr.val)

      if (curr.left) queue.push(curr.left)
      if (curr.right) queue.push(curr.right)
    }

    console.log(group) // Process group or handle result of current group
  }
}

Operations

Next is to build a class for managing a binary tree as a whole. Some common operations might be to get the height, add, remove, or search. You could even include any of the traversal methods to get the tree represented as an array in any of the traversal orders covered previously. I'll start with each method, then present the entire class to summarize.

Getting the Tree's Height

This one is the easiest of the methods as we only need to DFS to the deepest level and keep track of a maximum along the way. Recursively the managing of that is super simple. The iterative approach is little more involved, but that is the one I like to implement because it demonstrates another technique that comes up with trees where a stack needs to store more information (which is what would have been stored in the recursive call stack implicitly):

height() {
  let maxHeight = 0
  if (!this.root) return maxHeight

  let stack = [[this.root, 1]]

  while (stack.length > 0) {
    let [curr, currHeight] = stack.pop()!

    maxHeight = Math.max(maxHeight, currHeight)

    if (curr.left) stack.push([curr.left, currHeight + 1])
    if (curr.right) stack.push([curr.right, currHeight + 1])
  }

  return maxHeight
}

Searching for Values

In this context, searching means checking if a node exists. Any of the traversal methods can work, and I will implement a simple DFS pre-order. Note that if using arrays DFS will be better than BFS because shifting off of an array-based queue is slow:

search(val: T): BinaryTreeNode<T> | null {
  if (!this.root) return null

  let stack = [this.root]

  while (stack.length > 0) {
    const curr = stack.pop()!

    if (curr.val === val) return curr

    if (curr.left) stack.push(curr.left)
    if (curr.right) stack.push(curr.right)
  }

  return null
}

Adding Nodes

For plain binary trees with randomly ordered nodes, adding is fairly simple. It is not important to insert nodes anywhere, so the only thing to find is the first available spot. That position is usually identified as the upper-left-most empty spot, which is just the first null found using level-order traversal. Given that, adding a node can be written as:

add(val: T): void {
  if (!this.root) {
    this.root = new BinaryTreeNode(val)
    return
  }

  let queue = [this.root]

  while (queue.length > 0) {
    const curr = queue.shift()!

    if (curr.left) {
      queue.push(curr.left)
    } else {
      curr.left = new BinaryTreeNode(val)
      return
    }

    if (curr.right) {
      queue.push(curr.right)
    } else {
      curr.right = new BinaryTreeNode(val)
      return
    }
  }
}

Removing Nodes by Value

For previous tree algorithms, I've alluded to a preference that the left be prioritized (first with DFS, then with the beginning of each level in level-order). This is typical for balancing and avoiding complexity, and that approach will be important for removing nodes. Typically, removal involves finding the first occurrence of a provided value if it exists, and removing it. However, trees are nonlinear and the node to be removed could have more than one child. To handle that, some node must be selected to move up the tree to fill the empty position. Since order doesn't matter and adding looks for the first empty node (the first null found via level-order — which for compact trees should be the lower-right-most node), moving that node up will be the easiest.

The complexity of this method comes from the need to store the last node AND its parent so that it can be swapped using the last node and deleted off of the parent node later. Note that parent node is only updated with the most recent parent encountered (a node with left or right children). Here is the remove method:

remove(val: T): void {
  if (!this.root) return

  let queue: BinaryTreeNode<T>[] = [this.root]
  let nodeToBeRemoved: BinaryTreeNode<T> | null = null
  let lastNode: BinaryTreeNode<T> | null = null
  let parentOfLastNode: BinaryTreeNode<T> | null = null

  // Find first occurrence of value, the last node, and the last node's parent
  while (queue.length > 0) {
    const curr = queue.shift()!

    if (curr.val === val && !nodeToBeRemoved) {
      nodeToBeRemoved = curr
    }

    lastNode = curr

    if (curr.left) {
      queue.push(curr.left)
      parentOfLastNode = curr
    }

    if (curr.right) {
      queue.push(curr.right)
      parentOfLastNode = curr
    }
  }

  // Swap node values
  if (nodeToBeRemoved && lastNode) {
    nodeToBeRemoved.val = lastNode.val
  }

  // Delete last node
  if (parentOfLastNode) {
    if (parentOfLastNode.left === lastNode) {
      parentOfLastNode.left = null
    } else {
      parentOfLastNode.right = null
    }
  }
}

The Full Binary Tree Class

In summary, here is the full class:

class BinaryTree<T> {
  root: BinaryTreeNode<T> | null
  constructor(val?: T) {
    this.root = val ? new BinaryTreeNode(val) : null
  }

  height(): number {
    let maxHeight = 0
    if (!this.root) return maxHeight

    let stack: [BinaryTreeNode<T>, number][] = [[this.root, 1]]

    while (stack.length > 0) {
      let [curr, currHeight] = stack.pop()!

      maxHeight = Math.max(maxHeight, currHeight)

      if (curr.left) stack.push([curr.left, currHeight + 1])
      if (curr.right) stack.push([curr.right, currHeight + 1])
    }

    return maxHeight
  }

  search(val: T): BinaryTreeNode<T> | null {
    if (!this.root) return null

    let stack = [this.root]

    while (stack.length > 0) {
      const curr = stack.pop()!

      if (curr.val === val) return curr

      if (curr.left) stack.push(curr.left)
      if (curr.right) stack.push(curr.right)
    }

    return null
  }

  add(val: T): void {
    if (!this.root) {
      this.root = new BinaryTreeNode(val)
      return
    }

    let queue = [this.root]

    while (queue.length > 0) {
      const curr = queue.shift()!

      if (curr.left) {
        queue.push(curr.left)
      } else {
        curr.left = new BinaryTreeNode(val)
        return
      }

      if (curr.right) {
        queue.push(curr.right)
      } else {
        curr.right = new BinaryTreeNode(val)
        return
      }
    }
  }

  remove(val: T): void {
    if (!this.root) return

    let queue: BinaryTreeNode<T>[] = [this.root]
    let nodeToBeRemoved: BinaryTreeNode<T> | null = null
    let lastNode: BinaryTreeNode<T> | null = null
    let parentOfLastNode: BinaryTreeNode<T> | null = null

    // Find first occurrence of value, the last node, and the last node's parent
    while (queue.length > 0) {
      const curr = queue.shift()!

      if (curr.val === val && !nodeToBeRemoved) {
        nodeToBeRemoved = curr
      }

      lastNode = curr

      if (curr.left) {
        queue.push(curr.left)
        parentOfLastNode = curr
      }

      if (curr.right) {
        queue.push(curr.right)
        parentOfLastNode = curr
      }
    }

    // Swap node values
    if (nodeToBeRemoved && lastNode) {
      nodeToBeRemoved.val = lastNode.val
    }

    // Delete last node
    if (parentOfLastNode) {
      if (parentOfLastNode.left === lastNode) {
        parentOfLastNode.left = null
      } else {
        parentOfLastNode.right = null
      }
    }
  }
}