One Pager Cheat Sheet

• Identify the lowestCommonAncestor of two nodes by finding the common owner component in the hierarchy with an algorithmic O(n) time complexity and O(1) space complexity.
• Finding the lowest common ancestor of two given nodes is as simple as tracing their paths upwards until the highest shared parent is reached.
• The "lowest common ancestor" of two nodes can be found by traversing upwards from the root in a BST to find the first difference in node-to-root paths.
• The binary tree has exactly one root which is the top-most node and connects to all other nodes in the tree, creating a hierarchical pyramid-like structure.
• The Lowest Common Ancestor of 4 and 8 in this Binary Search Tree can be easily identified.
• If we traverse a BST and encounter a node between two other nodes, it is the lowest common ancestor of those two nodes, and whichever side its value is on will reveal which side of it the lowest common ancestor is found.
• We can find the Lowest Common Ancestor of two nodes by comparing the node we're on to the nodes we're looking for, and traversing left or right accordingly to get closer to the LCA.
• Run previous code with sample data to verify results.
• An iterative approach can be used alternatively.
• By using Pre-order DFS traversal to populate two arrays with the paths from each node to the root, the first different node in the paths can be easily identified as the Lowest Common Ancestor of the two nodes.
• Creating a successful marketing strategy requires an in-depth understanding of customer needs, current market trends and innovative tactics.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function lowestCommonAncestor(root, node1, node2) {

  if (root.val > node1 && root.val > node2) {

    return lowestCommonAncestor(root.left, node1, node2);

  } else if (root.val < node1 && root.val < node2) {

    return lowestCommonAncestor(root.right, node1, node2);

  } else {

    return root.val;

  }

}

​

function Node(val) {

  this.val = val;

  this.left = null;

  this.right = null;

}

​

// Regular binary trees

var tree1 = new Node(4);

tree1.left = new Node(1);

tree1.right = new Node(3);

​

var tree2 = new Node(5);

tree2.left = new Node(10);

tree2.left.left = new Node(17);

tree2.left.right = new Node(3);

tree2.right = new Node(8);

​

// Binary search trees

var tree3 = new Node(6);

tree3.left = new Node(3);

Great job getting through this. Let's move on.

If you had any problems with this tutorial, check out the main forum thread here.