Skip to content

Binary Trees

Jump to bottom
Nazmul Idris edited this page Aug 5, 2018 · 10 revisions

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.

/**
 * [Image of the generated tree](http://tinyurl.com/yckmlfkt)
 *        [A]
 *       /   \
 *     [B]    [C]
 *     / \    /  \
 *  [D]  [E] [F] [G]
 *               / \
 *             [H] [I]
 */
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)
    }
}

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

        // 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))

        // Add the node to the traversal list
        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).

BFS (pretty print)

/**
 * Traverses the binary tree nodes in a sorted order.
 */
fun <T> printBFSTraversal(root: Node<T>): String {

    val queue = LinkedList<Node<T>>()
    // Add first node
    queue.add(root)

    val mapVisitedDepth = mutableMapOf<Int, MutableList<T>>()
    // Use stack to create breadth first traversal
    while (queue.isNotEmpty()) {
        val currentNode = queue.poll()
        val depth = currentNode.depth

        // 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))

        // Decide whether to print crlf or not
        if (!mapVisitedDepth.containsKey(depth)) {
            mapVisitedDepth[depth] = mutableListOf()
        }
        mapVisitedDepth[depth]!!.add(currentNode.value)
    }

    val outputString = StringBuilder()

    for (entry in mapVisitedDepth) {
        outputString.append(entry.value.joinToString(", ", postfix = "\n"))
    }

    return outputString.toString()
}

Notes on implementation

  • This is almost identical to the code above. The main difference here is that a mapVisitedDepth Map is used in order to keep track of the depth of each traversed node, which can then be used to pretty print the output where a CRLF is added at the start of each new depth.

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).
  • A map is needed to keep track of nodes that have already been visited. This is different than what is required for the BFS algorithm.

Console output from running the code

Clone this wiki locally