Binary Trees

• Queues and stacks
• Ring Buffer
  • Implementation notes
  • Resources

Binary Trees

Node data structure

data class Node<T>(val value: T,
                   var leftNode: Node<T>?,
                   var rightNode: Node<T>?,
                   var depth: Int = 0) {
    fun link(left: Node<T>?, right: Node<T>?) = this.apply { 
        linkLeft(left).linkRight(right) 
    }

    fun linkLeft(left: Node<T>?) = this.apply { leftNode = left }

    fun linkRight(right: Node<T>?) = this.apply { rightNode = right }

    fun depth(value: Int) = this.apply { depth = value }

    /**
     * Nodes on the left are in yellow, and those on the right are blue.
     */
    override fun toString(): String {
        return StringBuffer().apply {
            append("{${value.toString().green()}")
            if (leftNode != null)
                append(", ${leftNode.toString().yellow()}")
            if (rightNode != null)
                append(", ${rightNode.toString().blue()}}")
        }.toString()
    }
}

Building the tree

The tree shown in the diagram above is built in code as follows.

fun buildTree(): Node<Char> {
    val a = Node('a', null, null)
    val b = Node('b', null, null)
    val c = Node('c', null, null)
    val d = Node('d', null, null)
    val e = Node('e', null, null)
    val f = Node('f', null, null)
    val g = Node('g', null, null)
    val h = Node('h', null, null)
    val i = Node('i', null, null)

    a.link(b, c)
    b.link(d, e)
    c.link(f, g)
    g.link(h, i)

    return a
}

Pre-order, in-order, and post-order recursive traversal

/**
 * A neat trick for pre-order traversals: starting from the root,
 * go around the tree counterclockwise. Print each node when you
 * pass its left side.
 */
fun <T> traversalPreOrder(node: Node<T>?, list: MutableList<T>) {
    if (node != null) {
        list.add(node.value)
        traversalPreOrder(node.leftNode, list)
        traversalPreOrder(node.rightNode, list)
    }
}

/**
 * A neat trick for in-order traversals: starting from the root,
 * go around the tree counterclockwise. Print each node when you
 * pass its bottom side.
 */
fun <T> traversalInOrder(node: Node<T>?, list: MutableList<T>) {
    if (node != null) {
        traversalInOrder(node.leftNode, list)
        list.add(node.value)
        traversalInOrder(node.rightNode, list)
    }
}

/**
 * A neat trick for post-order traversals: starting from the root,
 * go around the tree counterclockwise. Print each node when you
 * pass its right side.
 */
fun <T> traversalPostOrder(node: Node<T>?, list: MutableList<T>) {
    if (node != null) {
        traversalPostOrder(node.leftNode, list)
        traversalPostOrder(node.rightNode, list)
        list.add(node.value)
    }
}

DFS (depth first search) using a Stack

fun <T> depthFirstTraversal(root: Node<T>): MutableList<Node<T>> {
    val visitedMap = mutableMapOf<Node<T>, Boolean>()
    val stack = LinkedList<Node<T>>()
    val traversalList = mutableListOf<Node<T>>()

    // Add first node
    stack.push(root)

    // Use stack to create breadth first traversal
    while (stack.isNotEmpty()) {
        val currentNode = stack.pop()
        val depth = currentNode.depth

        // If the currentNode key can't be found in the map, then insert it
        visitedMap[currentNode] = visitedMap[currentNode] ?: false

        if (!visitedMap[currentNode]!!) {
            // Push right child to stack FIRST (so this will be processed LAST)
            if (currentNode.rightNode != null)
                stack.push(currentNode.rightNode!!.depth(depth + 1))

            // Push left child to stack LAST (so this will be processed FIRST)
            if (currentNode.leftNode != null)
                stack.push(currentNode.leftNode!!.depth(depth + 1))

            // Mark the current node visited and add to traversal list
            visitedMap[currentNode] = true
            traversalList.add(currentNode)
        }
    }

    return traversalList
}

Notes on the implementation

• The trick in the while loop is to leverage the LIFO nature of stack, in order to push the children on the right on top of the stack first, before the children on the left. Since the algorithm pops these items off the top of the stack, whatever was pushed last will get processed sooner (that what was pushed first). And this is what results in a depth first search.
• A depth field in the Node class is what keeps track of the number of branches from the root to this Node.
• The Deque interface supports both Stack and Queue ADTs (abstract data types).

BFS (breadth first search) using a Queue

/**
 * Traverses the binary tree nodes in a sorted order.
 */
fun <T> breadthFirstTraversal(root: Node<T>): MutableList<Node<T>> {
    val visitedMap = mutableMapOf<Node<T>, Boolean>()
    val queue = LinkedList<Node<T>>()
    val traversalList = mutableListOf<Node<T>>()

    // Add first node
    queue.add(root)

    // Use stack to create breadth first traversal
    while (queue.isNotEmpty()) {
        val currentNode = queue.poll()
        val depth = currentNode.depth

        // If the currentNode key can't be found in the map, then insert it
        visitedMap[currentNode] = visitedMap[currentNode] ?: false

        if (!visitedMap[currentNode]!!) {
            // Add left node first
            if (currentNode.leftNode != null)
                queue.add(currentNode.leftNode!!.depth(depth + 1))

            // Add right node next
            if (currentNode.rightNode != null)
                queue.add(currentNode.rightNode!!.depth(depth + 1))

            // Mark the current node visited and add to traversal list
            visitedMap[currentNode] = true
            traversalList.add(currentNode)
        }
    }

    return traversalList
}

Notes on the implementation

• BFS traversal of a binary tree results in a the nodes being visited in their sorted order.
• The trick in the while loop is leveraging the FIFO nature of the queue and allow the traversal of the tree from left node to right node, which results in a breadth first traversal.
• A depth field in the Node class is what keeps track of the number of branches from the root to this Node.
• The Deque interface supports both Stack and Queue ADTs (abstract data types).