LeetCode 1740: Find Distance in a Binary Tree Solution
Master LeetCode problem 1740 (Find Distance in a Binary Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1740. Find Distance in a Binary Tree
Problem Explanation
Explanation
To find the distance between two nodes in a binary tree, we first need to find the lowest common ancestor (LCA) of the two nodes. Once we have the LCA, we can calculate the distance as the sum of the distances from the LCA to each of the target nodes.
We can find the LCA using a recursive approach. Starting from the root, we traverse the tree in a depth-first manner. If we find either of the target nodes, we return that node. If we find both nodes on different sides of the current node, then the current node is the LCA. We recursively search in the left and right subtrees until we find both nodes on different sides or one of the nodes.
The distance between a node and its descendant can be calculated as the sum of the distances from the node to the descendant nodes.
Time complexity: O(n) where n is the number of nodes in the binary tree. Space complexity: O(n) for the recursive call stack.
Solution Code
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public int findDistance(TreeNode root, int p, int q) {
TreeNode lca = findLCA(root, p, q);
int distP = findDistanceToNode(lca, p, 0);
int distQ = findDistanceToNode(lca, q, 0);
return distP + distQ;
}
private TreeNode findLCA(TreeNode root, int p, int q) {
if (root == null || root.val == p || root.val == q) {
return root;
}
TreeNode left = findLCA(root.left, p, q);
TreeNode right = findLCA(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
private int findDistanceToNode(TreeNode root, int target, int distance) {
if (root == null) {
return -1;
}
if (root.val == target) {
return distance;
}
int left = findDistanceToNode(root.left, target, distance + 1);
int right = findDistanceToNode(root.right, target, distance + 1);
return Math.max(left, right);
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1740 (Find Distance in a Binary Tree)?
This page provides optimized solutions for LeetCode problem 1740 (Find Distance in a Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1740 (Find Distance in a Binary Tree)?
The time complexity for LeetCode 1740 (Find Distance in a Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1740 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1740 in Java, C++, or Python.