Lowest Common Ancestor in a Binary Tree
Updated
Problem statement
Given a binary tree root and two node values p and q, return the value of their lowest common ancestor.
An ancestor may be the node itself. The lowest common ancestor is the deepest node whose subtree contains both targets. The targets may be equal. This is an arbitrary binary tree, so its values need not follow binary-search-tree ordering.
The tree is displayed in level order with null for missing children. Both target values are present and node values are unique.
Function
lowestCommonAncestorValue(root: TreeNode, p: int, q: int) → intExamples
Example 1
root = [3,5,1,6,2,0,8,null,null,7,4]p = 5q = 1return = 3Values 5 and 1 are in different subtrees of node 3, so the answer is 3.
Example 2
root = [3,5,1,6,2,0,8,null,null,7,4]p = 5q = 4return = 5Node 5 is itself an ancestor of node 4, so the answer is 5.
Example 3
root = [9]p = 9q = 9return = 9Both targets identify the only node. A node is its own ancestor.
Constraints
- The input is a valid nonempty binary tree with 1 through 500 nodes.
- The level-order representation contains from 1 through 1001 entries.
- Every non-null node value is an integer between -1000000 and 1000000, inclusive.
- Node values are unique, and p and q both occur in the tree.
- Both p and q are integers between -1000000 and 1000000, inclusive.
More London Stock Exchange interview questions
- Implement a Queue Using an ArrayPHONE SCREEN · Seen Feb 2020
- Palindrome PartitioningPHONE SCREEN · Seen Feb 2020
- Two SumPHONE SCREEN · Seen Feb 2020
- Two Sum in a Sorted ArrayPHONE SCREEN · Seen Feb 2020
- Group Anagram StringsONSITE INTERVIEW · Seen Apr 2020
- Implement Key Equality and HashingONSITE INTERVIEW · Seen Apr 2020
Similar questions at other companies
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- House Robber IIIOkta · PHONE SCREENOkta interview questions
- Render a Task Tree from CSV RowsStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Validate Binary Search TreeKotak Mahindra Bank · PHONE SCREENKotak Mahindra Bank interview questions
- House Robber IIIGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Binary Tree Target-Sum PathsByteDance · PHONE SCREENByteDance interview questions
- House Robber IIIVisa · PHONE SCREENVisa interview questions
- Find All Paths for a Name in a File SystemThe Walt Disney Company · PHONE SCREENThe Walt Disney Company interview questions
- Validate a BST with a Custom ComparisonApple · PHONE SCREENApple interview questions
- Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions