The bottom view of a binary tree is the set of nodes that are visible when the tree is viewed from the bottom. In other words, it is the set of nodes that are at the bottom-most level of the tree for each horizontal distance. If there are multiple nodes at the same horizontal distance and the same bottom-most level, only the node with the smallest depth (i.e., the one closest to the root) is included in the bottom view. The bottom view of a binary tree can be visualized as follows:
20
/ \
8 22
/ \ \
5 3 25
/ \
10 14In this example, the bottom view of the binary tree is: 5 10 3 14 25. Note that the nodes 8 and 22 are not included in the bottom view, because they are not at the bottom-most level for their respective horizontal distances.
Kotlin
class TreeNode(val `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
fun bottomView(root: TreeNode?): List<Int> {
val result = mutableListOf<Int>()
if (root == null) {
return result
}
// Create a map to store the horizontal distance and bottom-most node
val map = mutableMapOf<Int, Int>()
// Create a queue to perform level order traversal
val queue = LinkedList<Pair<TreeNode, Int>>()
queue.offer(Pair(root, 0))
while (queue.isNotEmpty()) {
val size = queue.size
for (i in 0 until size) {
val (node, hd) = queue.poll()
// Update the bottom-most node for the current horizontal distance
map[hd] = node.`val`
// Add the left child to the queue with the horizontal distance hd-1
node.left?.let {
queue.offer(Pair(it, hd-1))
}
// Add the right child to the queue with the horizontal distance hd+1
node.right?.let {
queue.offer(Pair(it, hd+1))
}
}
}
// Sort the map by horizontal distance and add the bottom-most node for each distance to the result list
val sortedMap = map.toSortedMap()
for ((_, value) in sortedMap) {
result.add(value)
}
return result
}class TreeNode(valval: Int): This is a simple class that represents a node in a binary tree. Each node has an integer value and two child nodes (left and right).fun bottomView(root: TreeNode?): List<Int>: This is the main function that calculates the bottom view of the binary tree. It takes a root node as input and returns a list of integers representing the bottom-most nodes for each horizontal distance. If the root node is null, the function returns an empty list.val result = mutableListOf<Int>(): This creates an empty list to store the bottom-most nodes.if (root == null) { return result }: This checks if the root node is null. If it is null, the function returns the empty list.val map = mutableMapOf<Int, Int>(): This creates a mutable map to store the horizontal distance and bottom-most node for each level of the binary tree.val queue = LinkedList<Pair<TreeNode, Int>>(): This creates a queue to perform a level order traversal of the binary tree. Each element in the queue is a pair consisting of a tree node and its horizontal distance.queue.offer(Pair(root, 0)): This adds the root node and its horizontal distance (which is 0) to the queue.while (queue.isNotEmpty()) { ... }: This is a while loop that performs a level order traversal of the binary tree. It continues as long as the queue is not empty.val size = queue.size: This gets the number of nodes at the current level of the binary tree.for (i in 0 until size) { ... }: This is a for loop that iterates over all the nodes at the current level of the binary tree.val (node, hd) = queue.poll(): This gets the next node and its horizontal distance from the front of the queue.map[hd] = node.val“ : This updates the map with the bottom-most node for the current horizontal distance.node.left?.let { queue.offer(Pair(it, hd-1)) }: This adds the left child of the current node to the queue with a horizontal distance that is one less than the current distance.node.right?.let { queue.offer(Pair(it, hd+1)) }: This adds the right child of the current node to the queue with a horizontal distance that is one more than the current distance.val sortedMap = map.toSortedMap(): This creates a sorted map of the horizontal distances and bottom-most nodes.for ((_, value) in sortedMap) { result.add(value) }: This adds the bottom-most node for each horizontal distance to the result list.return result: This returns the result list of bottom-most nodes for the binary tree.
Kotlin
import java.util.*
class TreeNode(val `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
fun bottomView(root: TreeNode?): List<Int> {
val result = mutableListOf<Int>()
if (root == null) {
return result
}
// Create a map to store the horizontal distance and bottom-most node
val map = mutableMapOf<Int, Int>()
// Create a queue to perform level order traversal
val queue = LinkedList<Pair<TreeNode, Int>>()
queue.offer(Pair(root, 0))
while (queue.isNotEmpty()) {
val size = queue.size
for (i in 0 until size) {
val (node, hd) = queue.poll()
// Update the bottom-most node for the current horizontal distance
map[hd] = node.`val`
// Add the left child to the queue with the horizontal distance hd-1
node.left?.let {
queue.offer(Pair(it, hd-1))
}
// Add the right child to the queue with the horizontal distance hd+1
node.right?.let {
queue.offer(Pair(it, hd+1))
}
}
}
// Sort the map by horizontal distance and add the bottom-most node for each distance to the result list
val sortedMap = map.toSortedMap()
for ((_, value) in sortedMap) {
result.add(value)
}
return result
}
fun main() {
val root = TreeNode(20)
root.left = TreeNode(8)
root.right = TreeNode(22)
root.left!!.left = TreeNode(5)
root.left!!.right = TreeNode(3)
root.right!!.right = TreeNode(25)
root.left!!.right!!.left = TreeNode(10)
root.left!!.right!!.right = TreeNode(14)
val result = bottomView(root)
println(result) // Output: [5, 10, 3, 14, 25]
}Tree will be like :
20
/ \
8 22
/ \ \
5 3 25
/ \
10 14Output : [5, 10, 3, 14, 25]