Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.
_______6______ / \ ___2__ ___8__ / \ / \ 0 _4 7 9 / \ 3 5
Using the above tree as an example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. But how about LCA of nodes 2 and 4? Should it be 6 or 2?
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes vand w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).” Since a node can be a descendant of itself, the LCA of 2 and 4 should be 2, according to this definition.
Hint:
A top-down walk from the root of the tree is enough.
Solution:
There’s only three cases you need to consider.
- Both nodes are to the left of the tree.
- Both nodes are to the right of the tree.
- One node is on the left while the other is on the right.
For case 1), the LCA must be in its left subtree. Similar with case 2), LCA must be in its right subtree. For case 3), the current node must be the LCA.
Therefore, using a top-down approach, we traverse to the left/right subtree depends on the case of 1) or 2), until we reach case 3), which we concludes that we have found the LCA.
A careful reader might notice that we forgot to handle one extra case. What if the node itself is equal to one of the two nodes? This is the exact case from our earlier example! (The LCA of 2 and 4 should be 2). Therefore, we add case number 4):
The run time complexity is O(h), where h is the height of the BST. Translating this idea to code is straightforward (Note that we handle case 3) and 4) in the else statement to save us some extra typing ):
/* Function to find LCA of n1 and n2. The function assumes that both n1 and n2 are present in BST */ struct node* LCA(struct node* root, int n1, int n2) { if (root == NULL) return NULL; // If both n1 and n2 are smaller than root, then LCA lies in left if (root->data > n1 && root->data > n2) return LCA(root->left, n1, n2); // If both n1 and n2 are greater than root, then LCA lies in right if (root->data < n1 && root->data < n2) return LCA(root->right, n1, n2); return root; }
You should realize quickly that the above code contains tail recursion.
Time complexity of above solution is O(h) where h is height of tree. Also, the above solution requires O(h) extra space in function call stack for recursive function calls. We can avoid extra space using iterative solution.
struct node* LCA(struct node* root, int n1, int n2) { while (root != NULL) { // If both n1 and n2 are smaller than root, then LCA lies in left if (root->data > n1 && root->data > n2) root = root->left; // If both n1 and n2 are greater than root, then LCA lies in right else if (root->data < n1 && root->data < n2) root = root->right; else break; } return root; }
Reference:
http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-search-tree.html
相关推荐
1123.Lowest_Common_Ancestor_of_Deepest_Leaves最深叶节点的最近公共祖先【LeetCo
Range Minimum Query and Lowest Common Ancestor[翻译]1
Given a rooted binary tree, return the lowest common ancestor of its deepest leaves. Recall that: The node of a binary tree is a leaf if and only if it has no children The depth of the root of ...
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined ...
lowest common ancestor
This program calculates the lowest common multiple of two numbers using Euclid s algorithm. To do this we will read the two numbers and we do accounts required to calculate
非技术人员(包括传教士/儿童/老年人)的简单圣经免费软件小 1.2 兆下载与 OT+NT。 < 1 秒启动和搜索甚至在过时的最低公分母 486 上(1 GB 高清、640*480 分辨率、16 mb 内存、无 CD、28.8 调制解调器、Win95)
LCA(lowest common ancestor) ---, 5.贪婪 6. Manacher/KMP算法 (未完成) 7. 添加 8. 指针 滑动窗口 9.前缀总和 10.递归/DFS 11.棘手的方法 (未完成) 12. 堆栈 Monotonic_Stack 13. 14. 数据结构 每周比赛 第一...
tictax:Web服务的流序列分类 使用One Codex和EBI API从命令行或Python快速便捷地实现最低的祖先(LCA)分配。 以正确的方向吹风,每秒可发出约100个请求。... kmer-lca Lowest common ancestor sequ
针对已有方法不能正确求解基于ELCA(exclusive lowest common ancestor)语义的相关关键字节点(RKN,relevant keyword node)的问题,提出RKN的形式化定义及相应的RKN-Base算法。该算法通过顺序扫描每个关键字节点一次...
5.1.2 Lowest Common Ancestor (LCA) 53 5.1.3 Reduction from LCA to RMQ 56 5.1.4 From RMQ to LCA 57 5.1.5 An(N), O(1)> algorithm for the restricted RMQ 60 5.1.6 An AC programme 61 5.2 最长公共子序列LCS ...
5.1.2 Lowest Common Ancestor (LCA) 53 5.1.3 Reduction from LCA to RMQ 56 5.1.4 From RMQ to LCA 57 5.1.5 An(N), O(1)> algorithm for the restricted RMQ 60 5.1.6 An AC programme 61 5.2 最长公共子序列LCS ...
It begins with a global introduction, from the high-level view to the lowest common denominator (the chip itself), then moves on to the three main building blocks of an SOC (processor, memory, and ...
此指标依据输入参数显示周期内的最小价格。
要在控制台中运行特定问题,请转至文件test,将调用添加到测试函数( test() ),然后在控制台node <problem> (例如, node LeetcodeProblems/Lowest_Common_Ancestor_of_a_Binary_Tree.js )。 Leetcode问题 名称...
Lowest common multiple for Linux v2.13.6.
It incorporates extremal jammed states, including the densest packings, maximally random jammed states, and lowest-density jammed structures. Packings of identical spheres, spheres with a size ...
to disqualify it from use in all but the lowest-performance oscillators. Low noise oscillators are also highly desired in the digital world, of course. The continued drive toward higher clock ...
Embracing Diversity – Interconnecting Different Materials and Components for the Lowest $/Gb W4HBeyond the Gold Box: The Future of Integrated Optics III W4H.1 Circuit Design Techniques For High Bit...
to enable a common design to scale across families for optimal power, performance, and cost. The Spartan®-7 family is the lowest density with the lowest cost entry point into the 7 series portfolio...