Binary Search Tree : Lowest Common Ancestor

Sort by

recency

|

758 Discussions

|

  • + 0 comments

    My C code 😁😎

    struct node *lca( struct node *root, int v1, int v2 ) {
        while(root != NULL){
            if(v1 < root->data && v2 < root->data){
                root = root->left;
            }else if(v1 > root->data && v2 > root->data){
                root = root->right;
            }else{
                break;
            }
        }
        return root;
    }
    
  • + 0 comments

    **i got this answer from the youtube **

    JAVA EASY Youtbe Solution

    import java.io.; import java.util.*;

    public class Solution {

    public static class Node
    {
        public int data ;
        public Node leftNode;
        public Node rightNode;
        public Node(int data)
        {
            this.data = data;
            this.leftNode = null;
            this.rightNode = null;
    
        }
    }
    
    
    public static Node buildTree(Node root,int data)
    {
        if(root == null)
        {
            root = new Node(data);
            return root;
        }
    
        if(root.data > data)
        {
            root.leftNode = buildTree(root.leftNode, data);
        }
        if(root.data<data)
        {
            root.rightNode = buildTree(root.rightNode, data);
        }
        return root;
    }
    
    public static Node lca(Node root,int a,int b)
    {
        if(root.data < a && root.data < b)
        {
            return lca(root.rightNode,a,b);
        }
        if(root.data > a && root.data > b)
        {
            return lca(root.leftNode,a,b);
        }
        return root;
    }
    
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc=  new Scanner(System.in);
            Node root = null;
            int n = sc.nextInt();
            int i=0;
            while(i<n)
            {
                i++;
                int inp = sc.nextInt();
                root = buildTree(root, inp);
            }
            int a,b;
            a=sc.nextInt();b=sc.nextInt();
            Node lcaNode = lca(root, a, b);
            System.out.println(lcaNode.data);
            sc.close();
    
    
    }
    

    }

  • + 0 comments

    **i got this answer from the youtube **

    import java.io.; import java.util.*;

    public class Solution {

    public static class Node
    {
        public int data ;
        public Node leftNode;
        public Node rightNode;
        public Node(int data)
        {
            this.data = data;
            this.leftNode = null;
            this.rightNode = null;
    
        }
    }
    
    
    public static Node buildTree(Node root,int data)
    {
        if(root == null)
        {
            root = new Node(data);
            return root;
        }
    
        if(root.data > data)
        {
            root.leftNode = buildTree(root.leftNode, data);
        }
        if(root.data<data)
        {
            root.rightNode = buildTree(root.rightNode, data);
        }
        return root;
    }
    
    public static Node lca(Node root,int a,int b)
    {
        if(root.data < a && root.data < b)
        {
            return lca(root.rightNode,a,b);
        }
        if(root.data > a && root.data > b)
        {
            return lca(root.leftNode,a,b);
        }
        return root;
    }
    
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc=  new Scanner(System.in);
            Node root = null;
            int n = sc.nextInt();
            int i=0;
            while(i<n)
            {
                i++;
                int inp = sc.nextInt();
                root = buildTree(root, inp);
            }
            int a,b;
            a=sc.nextInt();b=sc.nextInt();
            Node lcaNode = lca(root, a, b);
            System.out.println(lcaNode.data);
            sc.close();
    
    
    }
    

    }

  • + 0 comments

    My solution was straight forward. keep going down the tree till both values change paths. They will have new ancestors each time the go down the tree and same path. the moment they separate ways is when you return that node at which they separated

  • + 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!