Binary Search Tree : Lowest Common Ancestor

  • + 0 comments

    My iterative approach

    public static Node lca(Node root, int v1, int v2) {
            if (root == null)
                return null;
            Set<Node> set = new HashSet<>();
            set.add(root);
            Node node = root;
            while (node.data != v1) {
                node = v1 < node.data ? node.left : node.right;
                set.add(node);
            }
            set.add(node);
            Node n = root;
            node = root;
            while (set.contains(node)) {
                n = node;
                node = v2 < node.data ? node.left : node.right;
            }
            return n;
        }