• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# lowest common ancestor bst

a guest Oct 21st, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /**
2.  * Definition for a binary tree node.
3.  * public class TreeNode {
4.  *     int val;
5.  *     TreeNode left;
6.  *     TreeNode right;
7.  *     TreeNode(int x) { val = x; }
8.  * map.contains
9.  */
10. class Solution {
11.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
12.         //map to hold parent-child relationships and be able to backtrack
13.         Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();
14.         //stack for traversing the tree, pushing children and popping in a while loop
15.         Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
16.
17.         //put the initial values
18.         map.put(root, null);
19.         stack.push(root);
20.
21.         //fill out the map with all nodes until it has both p and q
22.         while (!map.containsKey(p) || !map.containsKey(q)){
23.             if (!stack.isEmpty()){
24.                 TreeNode node = stack.pop();
25.                 if (node.left != null){
26.                     map.put(node.left, node);
27.                     stack.push(node.left);
28.                 }
29.                 if (node.right != null){
30.                     map.put(node.right, node);
31.                     stack.push(node.right);
32.                 }
33.             }
34.         }
35.
36.         //map now has all nodes up to p and q, now lets filter them out
37.         //set to hold unique parents of P as we backtrack on the map
38.         Set<TreeNode> pParents = new HashSet<TreeNode>();
39.         //node to hold p's highest parent (null, since the root's parent is null)
40.         TreeNode pParent = map.get(p);
42.         while (pParent != null){
44.             pParent = map.get(pParent);
45.         }
46.
47.         //now that we have all of p's parents in a set, lets return the first parent of q
48.         //that appears in that set (thus, getting the lowest common ancestor)
49.         TreeNode qParent = map.get(q);
50.         while(!pParents.contains(qParent)){
51.             qParent = map.get(q);
52.         }
53.
54.         //since the while loop stopped, qParent is suddenly in the ancestors set of p
55.         //so its the first occurance of a shared parent
56.         return qParent;
57.
58.     }
59. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top