Top View of Binary Tree in Kotlin

by

The top view of a binary tree is the set of nodes that are visible when we look at the tree from the top. To be more precise, the top view of a binary tree is the set of nodes that are visible when we project the tree onto a vertical plane and look at the nodes from the top of that plane.

Here’s an example to illustrate this concept:

         1
       /   \
      2     3
       \   / \
        4 5   6

If we look at the binary tree from the top, we would see the following set of nodes: 2 1 3 6

This is because the nodes 2, 1, 3, and 6 are the first nodes that we encounter when we traverse the binary tree from left to right along each level.

Note that the top view of a binary tree can have nodes from both the left and right subtrees, as well as the root node. Additionally, if there are nodes at the same horizontal distance from the root, we choose the one that appears first in the traversal.

Kotlin
fun topView(root: TreeNode?) {
    if (root == null) return

    val map = mutableMapOf<Int, Int>()  // to store the horizontal distance and node value

    val queue = ArrayDeque<Pair<TreeNode, Int>>()
    queue.addLast(root to 0) // add root node and horizontal distance 0 to the queue

    while (queue.isNotEmpty()) {
        val (node, hd) = queue.removeFirst()

        // if this is the first time we are visiting a node at this horizontal distance,
        // add it to the map
        if (!map.containsKey(hd)) {
            map[hd] = node.`val`
        }

        // add left and right children to the queue with horizontal distance
        // one less and one more than their parent node respectively
        node.left?.let { queue.addLast(it to hd - 1) }
        node.right?.let { queue.addLast(it to hd + 1) }
    }

    // print the node values in ascending order of their horizontal distance
    map.toSortedMap().values.forEach { print("$it ") }
}

topView function takes a binary tree node root as input and prints the top view of the binary tree in ascending order of their horizontal distance.

The function first checks if the input root is null, and if it is, returns from the function.

If the input root is not null, the function creates a mutable map called map to store the horizontal distance and node value pairs for the nodes in the top view.

The function then creates a queue called queue to store the nodes to be processed in a level-wise manner. It starts by adding a pair containing the root node and horizontal distance 0 to the queue.

The function then enters a while loop that continues until the queue is empty. In each iteration of the loop, the function processes one node from the queue. It first removes the node and its horizontal distance from the front of the queue using queue.removeFirst().

The function then checks if we have visited a node at this horizontal distance before by checking if the map already contains a key for this horizontal distance using map.containsKey(hd). If this is the first time we are visiting a node at this horizontal distance, we add it to the map using map[hd] = node.val“.

Finally, the function checks if the current node has any non-null children, and if it does, adds them to the end of the queue with a horizontal distance one less and one more than their parent node respectively. Note that the function adds the left child first, followed by the right child, so that the nodes in the current level are processed from left to right.

Once all the nodes in the binary tree have been processed, the function loops through the values of the map in ascending order of their keys (i.e., their horizontal distance), and prints them separated by a space using print("$it ").

This prints the values of the nodes in the top view of the binary tree in the desired order.

Kotlin
class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}
fun topView(root: TreeNode?) {
    if (root == null) return

    val map = mutableMapOf<Int, Int>()  // to store the horizontal distance and node value

    val queue = ArrayDeque<Pair<TreeNode, Int>>()
    queue.addLast(root to 0) // add root node and horizontal distance 0 to the queue

    while (queue.isNotEmpty()) {
        val (node, hd) = queue.removeFirst()

        // if this is the first time we are visiting a node at this horizontal distance,
        // add it to the map
        if (!map.containsKey(hd)) {
            map[hd] = node.`val`
        }

        // add left and right children to the queue with horizontal distance
        // one less and one more than their parent node respectively
        node.left?.let { queue.addLast(it to hd - 1) }
        node.right?.let { queue.addLast(it to hd + 1) }
    }

    // print the node values in ascending order of their horizontal distance
    map.toSortedMap().values.forEach { print("$it ") }
}

fun main() {
    // Create example binary tree
    val root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left?.right = TreeNode(4)
    root.right?.left = TreeNode(5)
    root.right?.right = TreeNode(6)
    
    // Print top view
    println("Top view of tree: ")
	topView(root)

}

Tree :

         1
       /   \
      2     3
       \   / \
        4 5   6

Output : Top view of tree: 2 1 3 6

Leave a Comment