LinkedIn·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

LinkedIn SWE interview with a tree problem that sounds straightforward until you realize there's no root pointer handed to you. The key insight is basically the linked list intersection trick in disguise, which I did not see coming.

Questions Asked (1)

Given two nodes in a binary tree where each node has a parent pointer, find their lowest common ancestor without access to the root.

Algorithms & Data Structures

Author's notes

I stared at this for a bit because my brain kept wanting to do the standard LCA recursion from the root, which you just...

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Since we don't have the root, we can't use the standard recursive approach. Instead, we can find the depth of each node by traversing up to the root using parent pointers, then align the deeper node by moving up until both nodes are at the same depth, and finally move both up simultaneously until they meet at the LCA. Alternatively, we can use a hash set to store ancestors of one node and check the other node's ancestors.

Pro tip: Discuss the trade-offs between the two approaches: the two-pointer method uses O(1) extra space but requires two passes to compute depths, while the hash set method uses O(h) space but may be simpler to implement. Mentioning these trade-offs shows depth of understanding.

1. Clarify the problem and constraints

Confirm that each node has a parent pointer, and we are given two nodes (not necessarily distinct). Ask if the nodes are guaranteed to be in the same tree and if the tree is binary (though the solution works for any tree with parent pointers).

2. Choose an approach

Decide between the two-pointer depth alignment method and the hash set method. Explain the chosen approach and why it's suitable given the constraints (e.g., space vs. time trade-offs).

3. Implement the chosen approach

For the two-pointer method: write a function to compute the depth of a node by traversing parent pointers to the root. Then align depths and move both pointers up until they meet. For the hash set method: traverse from one node to the root, storing each node in a set, then traverse from the other node until a node is found in the set.

4. Analyze time and space complexity

State the time complexity: O(h) for both methods, where h is the height of the tree. Space complexity: O(1) for two-pointer, O(h) for hash set. Discuss worst-case scenarios (e.g., skewed tree).

5. Test with edge cases

Consider edge cases: one node is an ancestor of the other, the nodes are the same, the tree is a single node, or the nodes are in different trees (if not guaranteed). Walk through how the algorithm handles these.

Key Points to Mention

The absence of a root means we must rely on parent pointers to traverse upwards.
Depth calculation: traverse from node to root to find depth, which takes O(h) time.
Two-pointer technique: align depths by moving the deeper node up, then move both up until they meet.
Hash set alternative: store all ancestors of one node in a set, then check the other node's ancestors.
Time complexity: O(h) for both approaches, where h is the height of the tree.
Space complexity: O(1) for two-pointer, O(h) for hash set; discuss trade-offs.
Edge cases: one node is ancestor of the other, nodes are identical, skewed trees.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.