Binary Tree

A Binary Tree is an abstract data struture that is made up of a root node and a left and right subtree. A node can have zero, one or two child nodes.

Types of Binary Trees

Objectives

• To be able to be familiar with various terms on a Binary Tree.
• To be able to implement a Binary Tree Node.
• To be able to use Breadth-First Traversal to print the values of a Binary Tree.
• To be able to use Depth-First In-Order traversal to print the values of a Binary Tree.
• To be able to use Depth-First Pre-Order traversal to print the values of a Binary Tree.
• To be able to use Depth-First Post-Order traversal to print the values of a Binary Tree.
• To be able to determine the height or the maximum depth of a Binary Tree.
• To be able to determine the diameter or width of a Binary Tree.

Link to completed Binary Tree

Tree Structure Vocabulary

• root
• subtree
• ancestor (a is an ancestor of b if there is a path to b where a is the root node)
• descendents
• parent node
• leaf (a node that doen't have any children)
• depth or level (number of edges from the root node to a given node)
• height (number of edges from the root node to the furthest leaf node)
• diameter or width (the longest distance between any two nodes in a tree)

Components of a Binary Tree Node

• data type it holds e.g Int or String etc
• a pointer to a left child node
• a pointer to a right child node

Common Operations

• Traversal
• Insertion
• Deletion

Binary Tree Node

class BinaryTreeNode<T> {
  var value: T
  var left: BinaryTreeNode?
  var right: BinaryTreeNode?
  init(_ value: T) {
    self.value = value
  }
}

Binary Tree

/*
        8
      /   \
     11    4
    /  \    \
   7   30    6
*/

Some facts about this Binary Tree:

• The height of the tree is 2, we count the edges between each node from the deepest leaf node.
• The depth of node 4 to the root is 1, again here we count the edges.
• This in NOT a Binary Search Tree as the values in the left subtree is not all less than the root and also the rules for a BST on the right subtree does not hold as node 4 and 6 should be greater than the root's value 8.

Traversing a Tree

The are 4 ways to traverse (iterate through each element of) a Binary Tree.

• Breadth-First Order traversal or Level-order traversal
• Depth-First Order Traversal - In-Order (left, root, right)
• Depth-First Order Traversal - Pre-Order (root, left, right)
• Depth-First Order Traversal - Post-Order (left, right, root)

Breadth-First Order traversal or Level-order traversal

With Bredth-First traversal a Queue is used since we want to print nodes by levels in which we visit them. We use the Queue to enqueue nodes and dequeue in the order we visited them. This ensures that we visit each node by the level in which it appears.

/*
        8
      /   \
     11    4
    /  \    \
   7   30    6
*/

The expected output when using Breadth-First Traversal is 8 11 4 7 30 6.

Queue

struct Queue<T> {
  private var elements = [T]()
  
  public var isEmpty: Bool {
    return elements.isEmpty
  }
  
  public var peek: T? {
    return elements.first
  }
  
  mutating func enqueue(_ element: T) {
    elements.append(element)
  }
  
  mutating func dequeue() -> T? { // see Queue lesson for more optimized dequeue https://github.com/alexpaul/Queue
    guard !elements.isEmpty else {
      return nil
    }
    return elements.removeFirst()
  }
}

Breadth-First Order traversal

/*
        8
      /   \
     11    4
    /  \    \
   7   30    6
*/

func breadthFirstTraversal<T>(_ treeNode: BinaryTreeNode<T>?) {
  var queue = Queue<BinaryTreeNode<T>>()
  guard let treeNode = treeNode else {
    return
  }
  queue.enqueue(treeNode)
  print(treeNode.value)
  while let node = queue.dequeue() {
    if let left = node.left {
      print(left.value)
      queue.enqueue(left)
    }
    if let right = node.right {
      print(right.value)
      queue.enqueue(right)
    }
  }
}

let rootNode = BinaryTreeNode(8)
let elevenNode = BinaryTreeNode(11)
let fourNode = BinaryTreeNode(4)
let sevenNode = BinaryTreeNode(7)
let thirtyNode = BinaryTreeNode(30)
let sixNode = BinaryTreeNode(6)

rootNode.left = elevenNode
rootNode.right = fourNode
elevenNode.left = sevenNode
elevenNode.right = thirtyNode
fourNode.right = sixNode

breadthFirstTraversal(rootNode)
// 8 11 4 7 30 6

Depth-First Order Traversal - In-Order

Review with Stacks and Recursion. If we are using recursion on a given problem keep in mind that we are using an implicit stack.

Write a function that takes a Binary Tree node and prints all its values

func inOrderTraversal<T>(_ root: BinaryTreeNode<T>?) {
  guard let root = root else { return }
  inOrderTraversal(root.left)
  print(root.value)
  inOrderTraversal(root.right)
}

/*
        8
      /   \
     11    4
    /  \    \
   7   30    6
*/

inOrderTraversal(rootNode) // 7 11 30 8 4 6

Write a function that takes a Binary Tree node and captures its values via a closure

func inOrderTraversal<T>(_ root: BinaryTreeNode<T>?, visit: (BinaryTreeNode<T>) -> ()) {
  guard let root = root else { return }
  inOrderTraversal(root.left, visit: visit)
  visit(root)
  inOrderTraversal(root.right, visit: visit)
}

inOrderTraversal(rootNode) { (node) in
  print(node.value) // 7 11 30 8 4 6
}

Extend Binary Tree node and write a funciton that captures all its values via a closure

extension BinaryTreeNode {
  func inOrderTraversal(_ visit: (BinaryTreeNode<T>) -> ()) {
    left?.inOrderTraversal(visit)
    visit(self)
    right?.inOrderTraversal(visit)
  }
}

rootNode.inOrderTraversal { (node) in
  print(node.value) // 7 11 30 8 4 6
}

In-order traversal can be used to find out if a given binary tree is a binary search tree, i.e in ascending order.

Depth-First Order Traversal - Post-Order

Write a function that take a Binary Tree node and prints the values using post-order traversal

/*
        8
      /   \
     11    4
    /  \    \
   7   30    6
*/

func postOrderTraversal<T>(_ root: BinaryTreeNode<T>?) {
  guard let root = root else { return }
  postOrderTraversal(root.left)
  postOrderTraversal(root.right)
  print(root.value, terminator: " ")
}

postOrderTraversal(rootNode) // 7 30 11 6 4 8

Post-order traversal can be used to delete a tree.

Depth-First Order Traversal - Pre-Order

/*
        8
      /   \
     11    4
    /  \    \
   7   30    6
*/

func preOrderTraversal<T>(_ root: BinaryTreeNode<T>?) {
  guard let root = root else { return }
  print(root.value, terminator: " ")
  preOrderTraversal(root.left)
  preOrderTraversal(root.right)
}

preOrderTraversal(rootNode) // 8 11 7 30 4 6

Pre-order traversal can be used to make a copy of a tree.

Height of the tree or maximum depth of a Binary Tree

/*
        8 = height of root is 1
      /   \
     11    4
    /  \    \
   7   30    6 = height is 3
*/

func height<T>(_ root: BinaryTreeNode<T>?) -> Int {
  guard let root = root else {
    return 0
  }
  var leftHeight = 0
  var rightHeight = 0
  if let leftChild = root.left {
    leftHeight = height(leftChild)
  }
  if let rightChild = root.right {
    rightHeight = height(rightChild)
  }
  // we start counting from 1, which represents the root
  // we increment each recursive call by 1
  return 1 + max(leftHeight, rightHeight)
}

height(rootNode) // 3 

Or we can write it using this shorter method below

func maxDepth<T>(_ root: BinaryTreeNode<T>?) -> Int {
  guard let root = root else { return 0 }
  return 1 + max(maxDepth(root.left), maxDepth(root.right))
}

maxDepth(rootNode) // 3

Diameter or Width of a Binary Tree

The diameter of the width of a Binary Tree is the longest path between two leaves. Those two leaves does not have to pass through the root. See sketch below:

func diameter<T>(_ root: BinaryTreeNode<T>?) -> Int {
  guard let root = root else { return 0 }
  
  let leftHeight = height(root.left)
  let rightHeight = height(root.right)
  
  let leftDiameter = diameter(root.left)
  let rightDiameter = diameter(root.right)
    
  return max(1 + leftHeight + rightHeight, max(leftDiameter, rightDiameter))
}

func height<T>(_ root: BinaryTreeNode<T>?) -> Int {
  guard let root = root else { return 0 }
  return 1 + max(height(root.left), height(root.right))
}


/*
        8
      /   \
     11    4
    /  \    \
   7   30    6
*/


// 7 11 8 4 6 = 5

// 30 11 8 4 6 = 5



/*
              2
            /   \
           12   18
          /  \
         17   36
        / \     \
       5   9     23
          /     /  \
         16    1   10
          \         /
           14      3
*/

let grassRoot = BinaryTreeNode(2)
let twelveNode = BinaryTreeNode(12)
let eighteenNode = BinaryTreeNode(18)
let seventeenNode = BinaryTreeNode(17)
let thirtysixNode = BinaryTreeNode(36)
let fiveNode = BinaryTreeNode(5)
let nineNode = BinaryTreeNode(9)
let twentyThreeNode = BinaryTreeNode(23)
let sixteenNode = BinaryTreeNode(6)
let oneNode = BinaryTreeNode(1)
let tenNode = BinaryTreeNode(10)
let fourteenNode = BinaryTreeNode(14)
let threeNode = BinaryTreeNode(3)

grassRoot.leftChild = twelveNode
grassRoot.rightChild = eighteenNode
twelveNode.leftChild = seventeenNode
twelveNode.rightChild = thirtysixNode
seventeenNode.leftChild = fiveNode
seventeenNode.rightChild = nineNode
nineNode.leftChild = sixteenNode
sixteenNode.rightChild = fourteenNode
thirtysixNode.rightChild = twentyThreeNode
twentyThreeNode.leftChild = oneNode
twentyThreeNode.rightChild = tenNode
tenNode.leftChild = threeNode


diameter(rootNode) // 5 - longest width passes through the root
diameter(grassRoot) // 9 - longest width DOES NOT pass through the root

Challenge

1. In-order Traversal

LeetCode

Resources

1. Wikipedia - Tree Data Structure
2. Wikipedia - Binary Tree
3. GeekForGeeks - Binary Tree Data Structure
4. HackerRank - Binary Trees and Binary Search Trees
5. RW - Swift Algorithm Club - Binary Tree
6. Video - HackerRank - Trees