Check if all leave Node are at same level of Binary Tree in Kotlin

by

To check if all leaf nodes of a binary tree are at the same level, we need to perform a level order traversal of the tree and keep track of the level of the first leaf node we encounter. Then, we check if all subsequent leaf nodes are at the same level as the first leaf node we encountered.

Here is an algorithm to check if all leaf nodes are at the same level:

  1. Initialize a queue to store the nodes of the binary tree.
  2. Enqueue the root node of the binary tree to the queue.
  3. Initialize a variable level to 0 to keep track of the level of the first leaf node.
  4. While the queue is not empty: a. Increment level by 1. b. Dequeue all nodes at the current level from the queue and enqueue their child nodes. c. If a dequeued node is a leaf node, then: i. If this is the first leaf node encountered, set level to its level. ii. Otherwise, if the level of this leaf node is not equal to level, return false.
  5. If all leaf nodes are at the same level, return true.

Example of Tree used in code:

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

Here is the Kotlin code to implement this algorithm:

Kotlin
data class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)
fun isLeaf(node: TreeNode?): Boolean {
    return node != null && node.left == null && node.right == null
}
fun areLeavesAtSameLevel(root: TreeNode): Boolean {
    val leafLevels = mutableSetOf<Int>() // keep track of levels of leaf nodes
    var level = -1 // initialize to -1 to detect first leaf node
    val queue = ArrayDeque<TreeNode>()
    queue.add(root)
    while (queue.isNotEmpty()) {
        val size = queue.size
        level++
        for (i in 0 until size) {
            val node = queue.removeFirst()
            if (node.left == null && node.right == null) {
                leafLevels.add(level)
            }
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
        }
    }
    return leafLevels.size == 1 // return true if there is only one level of leaf nodes
}
fun main() {
    // Construct a binary tree
    val root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left?.left = TreeNode(4)
    root.left?.right = TreeNode(5)
    root.right?.left = TreeNode(6)
    root.right?.right = TreeNode(7)
    // Check if all leaf nodes are at the same level
    if (areLeavesAtSameLevel(root)) {
        println("All leaf nodes are at the same level.")
    } else {
        println("Leaf nodes are not at the same level.")
    }
}
  1. The function takes a root node of a binary tree as input.
  2. It initializes a Set called leafLevels to keep track of the levels of leaf nodes encountered during the breadth-first traversal of the binary tree. It also initializes a variable called level to -1, which will be used to keep track of the current level of the tree during traversal.
  3. The function creates an ArrayDeque called queue and adds the root node to it.
  4. The function starts a while loop that continues as long as queue is not empty.
  5. Inside the while loop, the function gets the size of queue and initializes a for loop that iterates from 0 to the size of the queue minus one.
  6. Inside the for loop, the function removes the first node from queue and checks if it is a leaf node (i.e., if it has no left or right children). If the node is a leaf node, the function adds its level to the leafLevels set.
  7. The function then checks if the node has a left child or a right child, and adds them to queue if they exist.
  8. After the for loop completes, the function increments level to move on to the next level of the tree.
  9. The while loop continues until all nodes in the tree have been traversed.
  10. After traversal, the function checks if the size of leafLevels is 1. If it is, it means that all leaf nodes are at the same level, and the function returns true. If leafLevels has more than one element, it means that there are leaf nodes at different levels, and the function returns false.

The time complexity of the areLeavesAtSameLevel function is O(n), where n is the number of nodes in the binary tree. This is because the function traverses each node in the tree exactly once in a breadth-first manner.

The space complexity of the function is O(m), where m is the maximum number of nodes at a single level in the binary tree. This is because at most, all nodes at a single level will be stored in the queue data structure, which has a maximum size equal to the number of nodes at that level. In the worst case, when the binary tree is a complete binary tree, the maximum number of nodes at any level is (n/2), where n is the total number of nodes in the tree. Therefore, the space complexity of the function is O(n/2), which simplifies to O(n).

Leave a Comment