Construct Binary Tree from its Preorder and Inorder in Kotlin

To construct a binary tree from its inorder and preorder traversals, we can use the following algorithm:

Pick the first element of the preorder traversal and create a new tree node with that element as the root.
Find the position of the root node in the inorder traversal.
All the elements to the left of the root node in the inorder traversal will be in the left subtree of the root node, and all the elements to the right of the root node will be in the right subtree.
Recursively construct the left subtree by repeating steps 1 to 3 with the left part of the inorder traversal and the left part of the preorder traversal.
Recursively construct the right subtree by repeating steps 1 to 3 with the right part of the inorder traversal and the right part of the preorder traversal.
Return the root node of the binary tree.

Here’s an implementation of the algorithm in Kotlin:

Kotlin

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}
fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
    // Base case
    if (preorder.isEmpty() || inorder.isEmpty()) {
        return null
    }   
    // Create a new tree node with the first element of the preorder traversal as the root
    val root = TreeNode(preorder[0])    
    // Find the position of the root node in the inorder traversal
    val rootIndex = inorder.indexOf(root.`val`)    
    // Recursively construct the left and right subtrees
    root.left = buildTree(preorder.sliceArray(1 until rootIndex + 1), inorder.sliceArray(0 until rootIndex))
    root.right = buildTree(preorder.sliceArray(rootIndex + 1 until preorder.size), inorder.sliceArray(rootIndex + 1 until inorder.size))    
    // Return the root node of the binary tree
    return root
}
fun main() {
    val inorder = intArrayOf(4, 2, 5, 1, 3)
    val preorder = intArrayOf(1, 2, 4, 5, 3)
    val root = buildTree(preorder, inorder)
    // Print the inorder traversal of the binary tree
    printInorder(root)
}
fun printInorder(node: TreeNode?) {
    if (node == null) {
        return
    }   
    printInorder(node.left)
    print("${node.`val`} ")
    printInorder(node.right)
}

let’s walk through the example of constructing a binary tree from the following inorder and preorder traversals:

Inorder: 4, 2, 5, 1, 3 Preorder: 1, 2, 4, 5, 3

Here’s a step-by-step walkthrough of the buildTree function as it constructs the binary tree:

The function is called with the input arrays preorder = [1, 2, 4, 5, 3] and inorder = [4, 2, 5, 1, 3].
The function checks the base case: if either preorder or inorder is empty, it returns null. In this case, both arrays are non-empty, so the function continues.
The function creates a new TreeNode object with value 1, which will be the root of the binary tree.
The function finds the index of the root node (1) in the inorder traversal, which is 3. This tells us that all the elements to the left of 1 in the inorder traversal (i.e., 4, 2, and 5) will be in the left subtree of the root node, and all the elements to the right of 1 (i.e., 3) will be in the right subtree.
The function recursively constructs the left subtree by calling buildTree with the left part of the inorder traversal ([4, 2, 5]) and the left part of the preorder traversal ([2, 4, 5]).
The buildTree function is called again with the input arrays preorder = [2, 4, 5] and inorder = [4, 2, 5].
The function creates a new TreeNode object with value 2, which will be the root of the left subtree.
The function finds the index of the root node (2) in the inorder traversal, which is 1. This tells us that all the elements to the left of 2 in the inorder traversal (i.e., 4) will be in the left subtree of the root node, and all the elements to the right of 2 (i.e., 5) will be in the right subtree.
The function recursively constructs the left subtree of the left subtree by calling buildTree with the left part of the inorder traversal ([4]) and the left part of the preorder traversal ([4]).
The buildTree function is called again with the input arrays preorder = [4] and inorder = [4].
The function creates a new TreeNode object with value 4, which will be the root of the left subtree of the left subtree.
The function checks the base case and returns null, since both preorder and inorder are now empty.
The buildTree function returns the root node of the left subtree of the left subtree (i.e., the TreeNode object with value 4).
The function recursively constructs the right subtree of the left subtree by calling buildTree with the right part of the inorder traversal ([5]) and the right part of the preorder traversal ([5]).
The buildTree function is called again with the input arrays preorder = [5] and inorder = [5].
The function creates a new TreeNode object with value 5, which will be the root of the right subtree of the left subtree.
The function checks the base case and returns null, since both preorder and inorder are now empty.
The buildTree function returns the root node of the right subtree of the left subtree (i.e., the TreeNode object with value 5).
The function sets the left child of the root node (i.e., the TreeNode object with value 2) to the root node of the left subtree of the root node (i.e., the TreeNode object with value 4).
The function sets the right child of the root node (i.e., the TreeNode object with value 2) to the root node of the right subtree of the root node (i.e., the TreeNode object with value 5).
The function recursively constructs the right subtree by calling buildTree with the right part of the inorder traversal ([3]) and the right part of the preorder traversal ([3]).
The buildTree function is called again with the input arrays preorder = [3] and inorder = [3].
The function creates a new TreeNode object with value 3, which will be the root of the right subtree.
The function checks the base case and returns null, since both preorder and inorder are now empty.
The function sets the right child of the root node (i.e., the TreeNode object with value 1) to the root node of the right subtree (i.e., the TreeNode object with value 3).
The buildTree function returns the root node of the binary tree (i.e., the TreeNode object with value 1).

Here’s what the resulting binary tree looks like:

The time complexity of the buildTree function is O(n^2) in the worst case, where n is the number of nodes in the binary tree. This occurs when the binary tree is skewed, and each recursive call processes only one element at a time. However, in the average case, the time complexity is O(nlogn).

The space complexity of the buildTree function is O(n) due to the use of the HashMap data structure to store the indices of the elements in the inorder traversal. The recursive calls also add to the space complexity, but the maximum depth of the recursion is O(n) in the worst case, so the space complexity is still O(n).

Leave a Comment Cancel reply