Binary Search Tree : Lowest Common Ancestor

  • + 0 comments

    The Swift base code of this exercise is empty, so you can take this code and then implement your solution:

    import Foundation
    
    // Start of `Node` class
    class Node {
        var value: Int
        var left: Node?
        var right: Node?
    
        init(_ value : Int) {
            self.value  = value
        }
        
        func insert(_ value: Int) {
            if value < self.value {
                if let left {
                    left.insert(value)
                } else {
                    left = Node(value)    
                }
            } else if value > self.value {
                if let right {
                    right.insert(value)
                } else {
                    right = Node(value)
                }
            }
        }
        
        // Start of `lowestCommonAncestor` method
        func lowestCommonAncestor(_ node1: Int, _ node2: Int) -> Int? {
            
            // Enter your code here
    
        } // End of `lowestCommonAncestor` method
    }
    
    // Start of `Tree` class
    class Tree {
        var root: Node?
        
        func insert(_ value: Int) {
            if let root {
                root.insert(value)
            } else {
                root = Node(value)
            }
        }
    } // End of `Tree` class
    
    let tree = Tree()
    
    guard let _ = readLine(), // first line not needed
        let treeNodes = readLine()?.split(separator: " ").compactMap({ Int($0) }),
        let inputNodes = readLine()?.split(separator: " ").compactMap({ Int($0) }),
        inputNodes.count == 2
    else {
        print("ERROR: Invalid Input!")
        exit(-1)
    }
    
    treeNodes.forEach { node in
        tree.insert(node)
    }
    
    // Result:
    if let result = tree.root?.lowestCommonAncestor(inputNodes[0], inputNodes[1]) {
        print(result)
    } else {
        print("No LCA!")
    }
    

    Dear HackerRank team, please insert that base code or yours on this exercise.

    Thanks!