LCA(Lowest Common Ancestor) of binary tree - JAVA 


public class LowestCommonAncestor {
    static class TreeNode{
        private int data;        private TreeNode leftNode;        private TreeNode rightNode;
        public TreeNode(int data) {
            this.data = data;        }

        public int getData() {
            return data;        }

        public void setData(int data) {
            this.data = data;        }

        public TreeNode getLeftNode() {
            return leftNode;        }

        public void setLeftNode(TreeNode leftNode) {
            this.leftNode = leftNode;        }

        public TreeNode getRightNode() {
            return rightNode;        }

        public void setRightNode(TreeNode rightNode) {
            this.rightNode = rightNode;        }
    }


    public static TreeNode lca(TreeNode root, TreeNode x, TreeNode y){

        if(root == null)
            return null;
        if(root.getData() == x.getData() || root.getData() == y.getData())
            return root;
        TreeNode left = lca(root.getLeftNode(), x, y);        TreeNode right = lca(root.getRightNode(), x, y);
        if(left != null && right != null)
            return root;
        return left !=null ? left : right;    }

    public static void main(String[] args) {
        TreeNode tn1 = new TreeNode(2);
        TreeNode tn2 = new TreeNode(7);        TreeNode tn3 = new TreeNode(5);        tn1.setLeftNode(tn2);        tn1.setRightNode(tn3);
        TreeNode tn4 = new TreeNode(2);        TreeNode tn5 = new TreeNode(6);        tn2.setLeftNode(tn4);        tn2.setRightNode(tn5);
        TreeNode tn6 = new TreeNode(9);        tn3.setRightNode(tn6);
        TreeNode tn7 = new TreeNode(5);        TreeNode tn8 = new TreeNode(11);        tn5.setLeftNode(tn7);        tn5.setRightNode(tn8);
        TreeNode tn9 = new TreeNode(4);        tn6.setLeftNode(tn9);
        int data = lca(tn1, tn6, tn9).getData();        System.out.println(data);
    }
}




O/p: 9








































Comments











Post a Comment






























Popular posts from this blog










EJB - Stateful vs Stateless 





















  For  stateless session beans  the server can maintain a variable amount of instances in a pool. Each time a client requests such a stateless bean (e.g. through a method) a random instance is chosen to serve that request. That means if the client does two subsequent requests it is possible that two different instances of the stateless bean serve the requests. In fact there is no conversational state between the two requests. Also if the client disappears, the stateless bean does not get destroyed and can serve the next request from another client.   On the other hand a  stateful session bean  is closely connected to the client. Each instance is created and bounded to a single client and serves only requests from that particular client. So happens that if you do two subsequent requests on a stateful bean, your request will be served always from the same instance of the bean. That means you can maintain a conversational state between the requests. At the end of the li...








Read more










Mirror binay tree - Java





















 public class TreeNode {      private TreeNode left;      private TreeNode right;      private Object value;       public TreeNode getLeft() {          return left;      }       public TreeNode setLeft(TreeNode left) {          this.left = left;          return this;      }       public TreeNode getRight() {          return right;      }       public TreeNode setRight(TreeNode right) {          this.right = right;          return this;      }       public Object getValue() {          return value;      }       public TreeNode setValue(Object value) {          this.value = value;          return this;      }  }     public class Mirror {       public stat...








Read more