@Test public void shouldFindLCAWhenIsAFatherOfBothNodesIterative() { BinaryNode<Integer> root = new BinaryNode<Integer>(1); BinaryNode<Integer> n2 = new BinaryNode<Integer>(2); BinaryNode<Integer> n3 = new BinaryNode<Integer>(3); BinaryNode<Integer> n4 = new BinaryNode<Integer>(4); BinaryNode<Integer> n5 = new BinaryNode<Integer>(5); BinaryNode<Integer> n6 = new BinaryNode<Integer>(6); root.setLeft(n2); root.setRight(n3); n2.setLeft(n4); n2.setRight(n5); n4.setLeft(n6); BinaryNode result = lca.getIterative(root, n5, n6); assertEquals(n2, result); }
public BinaryNode getIterative(BinaryNode root, BinaryNode n1, BinaryNode n2) { validateInput(root, n1, n2); List<BinaryNode> pathToA = getPathTo(root, n1); List<BinaryNode> pathToB = getPathTo(root, n2); BinaryNode result = null; int size = Math.min(pathToA.size(), pathToB.size()); for (int i = 0; i < size; i++) { if (pathToA.get(i) != pathToB.get(i)) { result = pathToA.get(i - 1); break; } } return result; }
LowestCommonAncestor { public BinaryNode getIterative(BinaryNode root, BinaryNode n1, BinaryNode n2) { validateInput(root, n1, n2); List<BinaryNode> pathToA = getPathTo(root, n1); List<BinaryNode> pathToB = getPathTo(root, n2); BinaryNode result = null; int size = Math.min(pathToA.size(), pathToB.size()); for (int i = 0; i < size; i++) { if (pathToA.get(i) != pathToB.get(i)) { result = pathToA.get(i - 1); break; } } return result; } }
LowestCommonAncestor { public BinaryNode getIterative(BinaryNode root, BinaryNode n1, BinaryNode n2) { validateInput(root, n1, n2); List<BinaryNode> pathToA = getPathTo(root, n1); List<BinaryNode> pathToB = getPathTo(root, n2); BinaryNode result = null; int size = Math.min(pathToA.size(), pathToB.size()); for (int i = 0; i < size; i++) { if (pathToA.get(i) != pathToB.get(i)) { result = pathToA.get(i - 1); break; } } return result; }  }
LowestCommonAncestor { public BinaryNode getIterative(BinaryNode root, BinaryNode n1, BinaryNode n2) { validateInput(root, n1, n2); List<BinaryNode> pathToA = getPathTo(root, n1); List<BinaryNode> pathToB = getPathTo(root, n2); BinaryNode result = null; int size = Math.min(pathToA.size(), pathToB.size()); for (int i = 0; i < size; i++) { if (pathToA.get(i) != pathToB.get(i)) { result = pathToA.get(i - 1); break; } } return result; }  BinaryNode getRecursive(BinaryNode root, BinaryNode n1, BinaryNode n2); BinaryNode getIterative(BinaryNode root, BinaryNode n1, BinaryNode n2); }
LowestCommonAncestor { public BinaryNode getIterative(BinaryNode root, BinaryNode n1, BinaryNode n2) { validateInput(root, n1, n2); List<BinaryNode> pathToA = getPathTo(root, n1); List<BinaryNode> pathToB = getPathTo(root, n2); BinaryNode result = null; int size = Math.min(pathToA.size(), pathToB.size()); for (int i = 0; i < size; i++) { if (pathToA.get(i) != pathToB.get(i)) { result = pathToA.get(i - 1); break; } } return result; }  BinaryNode getRecursive(BinaryNode root, BinaryNode n1, BinaryNode n2); BinaryNode getIterative(BinaryNode root, BinaryNode n1, BinaryNode n2);  }