{"id":"0564be1e-4637-4679-92e8-ff799f71e3cb","name":" Lowest Common Ancestor Of A Binary Tree","description":"1. Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.\r\n2. According to the definition of LCA on Wikipedia: \r\nThe lowest common ancestor is defined between two nodes p and q as the lowest node in T that has \r\nboth p and q as descendants (where we allow a node to be a descendant of itself).\r\n3. If LCA does not exist in the tree print null.\r\n","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"1. The number of nodes in the tree is in the range [-1000, 1000].\r\n2. -109 &lt;= Node.val &lt;= 109\r\nAll Node.val are unique.\r\np != q\r\np and q may or may not exist in the tree.\r\n","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\r\nusing namespace std;\r\n\r\nclass TreeNode\r\n{\r\npublic:\r\n int val = 0;\r\n TreeNode* left = nullptr;\r\n TreeNode* right = nullptr;\r\n\r\n TreeNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nTreeNode* lowestCommonAncestor(TreeNode* root, int p, int q)\r\n{\r\n}\r\n\r\n// input_Section_====================================================================\r\n\r\nvoid display(TreeNode* node)\r\n{\r\n if (node == nullptr)\r\n return;\r\n\r\n string str = \"\";\r\n str += ((node->left != nullptr ? to_string(node->left->val) : \".\"));\r\n str += (\" -> \" + to_string(node->val) + \" <- \");\r\n str += ((node->right != nullptr ? to_string(node->right->val) : \".\"));\r\n\r\n cout << str << endl;\r\n\r\n display(node->left);\r\n display(node->right);\r\n}\r\n\r\nint idx = 0;\r\nTreeNode* deserialize(vector<string>& arr)\r\n{\r\n if (idx >= arr.size() || arr[idx].compare(\"null\") == 0)\r\n {\r\n idx++;\r\n return nullptr;\r\n }\r\n\r\n TreeNode* node = new TreeNode(stoi(arr[idx++]));\r\n node->left = deserialize(arr);\r\n node->right = deserialize(arr);\r\n\r\n return node;\r\n}\r\n\r\nTreeNode* deserialize(string s)\r\n{\r\n stringstream ss(s);\r\n string word;\r\n vector<string> arr;\r\n while (ss >> word)\r\n {\r\n arr.push_back(word);\r\n }\r\n return deserialize(arr);\r\n}\r\n\r\nvoid solve()\r\n{\r\n string s;\r\n cin >> s;\r\n TreeNode* root = deserialize(s);\r\n int p, q;\r\n cin >> p >> q;\r\n\r\n TreeNode* ans = lowestCommonAncestor(root, p, q);\r\n\r\n cout << (ans != nullptr ? \"null\" : ans->val) << endl;\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.*;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class TreeNode {\r\n int val = 0;\r\n TreeNode left = null;\r\n TreeNode right = null;\r\n\r\n TreeNode(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static TreeNode lowestCommonAncestor(TreeNode node, int p, int q) {\r\n\r\n }\r\n\r\n // input_section=================================================\r\n\r\n public static void display(TreeNode node) {\r\n if (node == null)\r\n return;\r\n\r\n StringBuilder sb = new StringBuilder();\r\n sb.append((node.left != null ? node.left.val : \".\"));\r\n sb.append(\" -> \" + node.val + \" <- \");\r\n sb.append((node.right != null ? node.right.val : \".\"));\r\n\r\n System.out.println(sb.toString());\r\n\r\n display(node.left);\r\n display(node.right);\r\n }\r\n\r\n public static int idx = 0;\r\n\r\n private static TreeNode deserialize(String[] arr) {\r\n if (idx >= arr.length || arr[idx].equals(\"null\")) {\r\n idx++;\r\n return null;\r\n }\r\n\r\n TreeNode node = new TreeNode(Integer.parseInt(arr[idx++]));\r\n node.left = deserialize(arr);\r\n node.right = deserialize(arr);\r\n\r\n return node;\r\n }\r\n\r\n public static TreeNode deserialize(String str) {\r\n String[] arr = str.split(\" \");\r\n return deserialize(arr);\r\n }\r\n\r\n public static void solve() {\r\n String str = scn.nextLine();\r\n TreeNode root = deserialize(str);\r\n\r\n int e1 = scn.nextInt();\r\n int e2 = scn.nextInt();\r\n\r\n TreeNode ans = lowestCommonAncestor(root, e1, e2);\r\n System.out.println(ans == null ? null : ans.val);\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"10 5 3 13 null null -2 null null 2 null 1 null null -3 null 11 null null\r\n13 3","sampleOutput":"3\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"65e3ea51-f2e6-4ff0-bbf0-1b909c34bd0e","name":" Lowest Common Ancestor Of A Binary Tree","slug":"lowest-common-ancestor-of-a-binary-tree","type":1}],"next":{"id":"5c6b1499-1fd3-4bf1-ad98-93d177dd30b7","name":"Lowest Common Ancestor A Binary Tree","type":3,"slug":"lowest-common-ancestor-a-binary-tree"},"prev":{"id":"169f316b-23bc-43a8-a4e9-98fa1c7dd00a","name":"All Possible Full Binary Tree","type":3,"slug":"all-possible-full-binary-tree"}}}

Lowest Common Ancestor Of A Binary Tree

1. Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. 2. According to the definition of LCA on Wikipedia: The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself). 3. If LCA does not exist in the tree print null.

{"id":"0564be1e-4637-4679-92e8-ff799f71e3cb","name":" Lowest Common Ancestor Of A Binary Tree","description":"1. Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.\r\n2. According to the definition of LCA on Wikipedia: \r\nThe lowest common ancestor is defined between two nodes p and q as the lowest node in T that has \r\nboth p and q as descendants (where we allow a node to be a descendant of itself).\r\n3. If LCA does not exist in the tree print null.\r\n","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"1. The number of nodes in the tree is in the range [-1000, 1000].\r\n2. -109 &lt;= Node.val &lt;= 109\r\nAll Node.val are unique.\r\np != q\r\np and q may or may not exist in the tree.\r\n","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\r\nusing namespace std;\r\n\r\nclass TreeNode\r\n{\r\npublic:\r\n int val = 0;\r\n TreeNode* left = nullptr;\r\n TreeNode* right = nullptr;\r\n\r\n TreeNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nTreeNode* lowestCommonAncestor(TreeNode* root, int p, int q)\r\n{\r\n}\r\n\r\n// input_Section_====================================================================\r\n\r\nvoid display(TreeNode* node)\r\n{\r\n if (node == nullptr)\r\n return;\r\n\r\n string str = \"\";\r\n str += ((node->left != nullptr ? to_string(node->left->val) : \".\"));\r\n str += (\" -> \" + to_string(node->val) + \" <- \");\r\n str += ((node->right != nullptr ? to_string(node->right->val) : \".\"));\r\n\r\n cout << str << endl;\r\n\r\n display(node->left);\r\n display(node->right);\r\n}\r\n\r\nint idx = 0;\r\nTreeNode* deserialize(vector<string>& arr)\r\n{\r\n if (idx >= arr.size() || arr[idx].compare(\"null\") == 0)\r\n {\r\n idx++;\r\n return nullptr;\r\n }\r\n\r\n TreeNode* node = new TreeNode(stoi(arr[idx++]));\r\n node->left = deserialize(arr);\r\n node->right = deserialize(arr);\r\n\r\n return node;\r\n}\r\n\r\nTreeNode* deserialize(string s)\r\n{\r\n stringstream ss(s);\r\n string word;\r\n vector<string> arr;\r\n while (ss >> word)\r\n {\r\n arr.push_back(word);\r\n }\r\n return deserialize(arr);\r\n}\r\n\r\nvoid solve()\r\n{\r\n string s;\r\n cin >> s;\r\n TreeNode* root = deserialize(s);\r\n int p, q;\r\n cin >> p >> q;\r\n\r\n TreeNode* ans = lowestCommonAncestor(root, p, q);\r\n\r\n cout << (ans != nullptr ? \"null\" : ans->val) << endl;\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.*;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class TreeNode {\r\n int val = 0;\r\n TreeNode left = null;\r\n TreeNode right = null;\r\n\r\n TreeNode(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static TreeNode lowestCommonAncestor(TreeNode node, int p, int q) {\r\n\r\n }\r\n\r\n // input_section=================================================\r\n\r\n public static void display(TreeNode node) {\r\n if (node == null)\r\n return;\r\n\r\n StringBuilder sb = new StringBuilder();\r\n sb.append((node.left != null ? node.left.val : \".\"));\r\n sb.append(\" -> \" + node.val + \" <- \");\r\n sb.append((node.right != null ? node.right.val : \".\"));\r\n\r\n System.out.println(sb.toString());\r\n\r\n display(node.left);\r\n display(node.right);\r\n }\r\n\r\n public static int idx = 0;\r\n\r\n private static TreeNode deserialize(String[] arr) {\r\n if (idx >= arr.length || arr[idx].equals(\"null\")) {\r\n idx++;\r\n return null;\r\n }\r\n\r\n TreeNode node = new TreeNode(Integer.parseInt(arr[idx++]));\r\n node.left = deserialize(arr);\r\n node.right = deserialize(arr);\r\n\r\n return node;\r\n }\r\n\r\n public static TreeNode deserialize(String str) {\r\n String[] arr = str.split(\" \");\r\n return deserialize(arr);\r\n }\r\n\r\n public static void solve() {\r\n String str = scn.nextLine();\r\n TreeNode root = deserialize(str);\r\n\r\n int e1 = scn.nextInt();\r\n int e2 = scn.nextInt();\r\n\r\n TreeNode ans = lowestCommonAncestor(root, e1, e2);\r\n System.out.println(ans == null ? null : ans.val);\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"10 5 3 13 null null -2 null null 2 null 1 null null -3 null 11 null null\r\n13 3","sampleOutput":"3\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"65e3ea51-f2e6-4ff0-bbf0-1b909c34bd0e","name":" Lowest Common Ancestor Of A Binary Tree","slug":"lowest-common-ancestor-of-a-binary-tree","type":1}],"next":{"id":"5c6b1499-1fd3-4bf1-ad98-93d177dd30b7","name":"Lowest Common Ancestor A Binary Tree","type":3,"slug":"lowest-common-ancestor-a-binary-tree"},"prev":{"id":"169f316b-23bc-43a8-a4e9-98fa1c7dd00a","name":"All Possible Full Binary Tree","type":3,"slug":"all-possible-full-binary-tree"}}}
plane

Editor


Loading...

Lowest Common Ancestor Of A Binary Tree

medium

1. Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. 2. According to the definition of LCA on Wikipedia: The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself). 3. If LCA does not exist in the tree print null.

Constraints

1. The number of nodes in the tree is in the range [-1000, 1000]. 2. -109 <= Node.val <= 109 All Node.val are unique. p != q p and q may or may not exist in the tree.

Format

Input

Input is managed for you.

Output

Output is managed for you.

Example

Sample Input

10 5 3 13 null null -2 null null 2 null 1 null null -3 null 11 null null 13 3

Sample Output

3

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode