1"use strict";(self.webpackChunk_N_E=self.webpackChunk_N_E||[]).push([[2982],{2982:function(e,n,t){t.r(n),t.d(n,{LowestCommonAncestorBinaryTree:function(){return l}});var r=t(88078),o=t(63969);let l={id:"lowest-common-ancestor-of-a-binary-tree",label:"Lowest Common Ancestor of a Binary Tree",description:"Find the lowest common ancestor (LCA) of two nodes in a binary tree. The LCA is the lowest node that has both p and q as descendants.",constraints:["The number of nodes is in the range $[2, 10^5]$.","$-10^9 \\leq \\text{Node.val} \\leq 10^9$","All `Node.val` are unique.","`p != q`","`p` and `q` will exist in the tree."],topics:["tree","depth-first-search","binary-tree"],companies:["Amazon","Facebook","Microsoft","LinkedIn","Apple","Bloomberg"],category:"Trees",difficulty:"Medium",code:{python:"class Solution:\n def lowestCommonAncestor(self, root: 'TreeNode', p: int, q: int) -> int:\n def dfs(node):\n if not node:\n return None\n if node.val == p or node.val == q:\n return node\n left = dfs(node.left)\n right = dfs(node.right)\n if left and right:\n return node\n return left or right\n return dfs(root).val",javascript:"var lowestCommonAncestor = function(root, p, q) {\n function dfs(node) {\n if (!node) return null;\n if (node.val === p || node.val === q) return node;\n const left = dfs(node.left);\n const right = dfs(node.right);\n if (left && right) return node;\n return left || right;\n }\n return dfs(root).val;\n};",typescript:"function lowestCommonAncestor(root: TreeNode | null, p: number, q: number): number {\n function dfs(node: TreeNode | null): TreeNode | null {\n if (!node) return null;\n if (node.val === p || node.val === q) return node;\n const left = dfs(node.left);\n const right = dfs(node.right);\n if (left && right) return node;\n return left || right;\n }\n return dfs(root)!.val;\n}",java:"class Solution {\n int p, q;\n public int lowestCommonAncestor(TreeNode root, int p, int q) {\n this.p = p;\n this.q = q;\n return dfs(root).val;\n }\n private TreeNode dfs(TreeNode node) {\n if (node == null) return null;\n if (node.val == p || node.val == q) return node;\n TreeNode left = dfs(node.left);\n TreeNode right = dfs(node.right);\n if (left != null && right != null) return node;\n return left != null ? left : right;\n }\n}",cpp:"class Solution {\npublic:\n int p, q;\n int lowestCommonAncestor(TreeNode* root, int p, int q) {\n this->p = p;\n this->q = q;\n return dfs(root)->val;\n }\n TreeNode* dfs(TreeNode* node) {\n if (!node) return nullptr;\n if (node->val == p || node->val == q) return node;\n TreeNode* left = dfs(node->left);\n TreeNode* right = dfs(node->right);\n if (left && right) return node;\n return left ? left : right;\n }\n};",csharp:"public class Solution {\n int p, q;\n public int LowestCommonAncestor(TreeNode root, int p, int q) {\n this.p = p;\n this.q = q;\n return Dfs(root).val;\n }\n private TreeNode Dfs(TreeNode node) {\n if (node == null) return null;\n if (node.val == p || node.val == q) return node;\n TreeNode left = Dfs(node.left);\n TreeNode right = Dfs(node.right);\n if (left != null && right != null) return node;\n return left ?? right;\n }\n}",go:"func lowestCommonAncestor(root *TreeNode, p int, q int) int {\n var dfs func(*TreeNode) *TreeNode\n dfs = func(node *TreeNode) *TreeNode {\n if node == nil {\n return nil\n }\n if node.Val == p || node.Val == q {\n return node\n }\n left := dfs(node.Left)\n right := dfs(node.Right)\n if left != nil && right != nil {\n return node\n }\n if left != nil {\n return left\n }\n return right\n }\n return dfs(root).Val\n}"},lineMapping:{python:{start_dfs:3,check_null:4,return_null:5,check_target:6,return_target:7,recurse_left:8,recurse_right:9,check_both:10,return_lca:11,return_found:12,final_return:13},javascript:{start_dfs:2,check_null:3,return_null:3,check_target:4,return_target:4,recurse_left:5,recurse_right:6,check_both:7,return_lca:7,return_found:8,final_return:10},typescript:{start_dfs:2,check_null:3,return_null:3,check_target:4,return_target:4,recurse_left:5,recurse_right:6,check_both:7,return_lca:7,return_found:8,final_return:10},java:{start_dfs:8,check_null:9,return_null:9,check_target:10,return_target:10,recurse_left:11,recurse_right:12,check_both:13,return_lca:13,return_found:14,final_return:6},cpp:{start_dfs:9,check_null:10,return_null:10,check_target:11,return_target:11,recurse_left:12,recurse_right:13,check_both:14,return_lca:14,return_found:15,final_return:7},csharp:{start_dfs:8,check_null:9,return_null:9,check_target:10,return_target:10,recurse_left:11,recurse_right:12,check_both:13,return_lca:13,return_found:14,final_return:6},go:{start_dfs:2,check_null:4,return_null:5,check_target:7,return_target:8,recurse_left:10,recurse_right:11,check_both:12,return_lca:13,return_found:15,final_return:18}}
1,presets:[{label:"Example 1",data:{root:[3,5,1,6,2,0,8,null,null,7,4],p:5,q:1},expected:"3"},{label:"Example 2",data:{root:[3,5,1,6,2,0,8,null,null,7,4],p:5,q:4},expected:"5"},{label:"Example 3",data:{root:[1,2],p:1,q:2},expected:"1"},{label:"Deep Tree",data:{root:[3,5,1,6,2,0,8,null,null,7,4],p:7,q:4},expected:"2"}],defaultInput:{root:[3,5,1,6,2,0,8,null,null,7,4],p:5,q:1},defaultExpected:"3",Renderer:r.LCABinaryTreeRenderer,functionSignature:{name:"lowestCommonAncestor",params:[{name:"root",type:"TreeNode"},{name:"p",type:"int"},{name:"q",type:"int"}],returnType:"int"},starterCode:{python:"# Definition for a binary tree node.\n# class TreeNode:\n# def __init__(self, x):\n# self.val = x\n# self.left = None\n# self.right = None\n\nclass Solution:\n def lowestCommonAncestor(self, root: 'TreeNode', p: int, q: int) -> int:\n # Write your solution here\n return 0",javascript:"/**\n * Definition for a binary tree node.\n * function TreeNode(val) {\n * this.val = val;\n * this.left = this.right = null;\n * }\n */\n/**\n * @param {TreeNode} root\n * @param {number} p\n * @param {number} q\n * @return {number}\n */\nvar lowestCommonAncestor = function(root, p, q) {\n // Write your solution here\n return 0;\n};",typescript:"/**\n * Definition for a binary tree node.\n * class TreeNode {\n * val: number\n * left: TreeNode | null\n * right: TreeNode | null\n * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null)\n * }\n */\nfunction lowestCommonAncestor(root: TreeNode | null, p: number, q: number): number {\n // Write your solution here\n return 0;\n}",java:"/**\n * Definition for a binary tree node.\n * public class TreeNode {\n * int val;\n * TreeNode left;\n * TreeNode right;\n * TreeNode(int x) { val = x; }\n * }\n */\nclass Solution {\n public int lowestCommonAncestor(TreeNode root, int p, int q) {\n // Write your solution here\n return 0;\n }\n}",cpp:"/**\n * Definition for a binary tree node.\n * struct TreeNode {\n * int val;\n * TreeNode *left;\n * TreeNode *right;\n * TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n * };\n */\nclass Solution {\npublic:\n int lowestCommonAncestor(TreeNode* root, int p, int q) {\n // Write your solution here\n return 0;\n }\n};",csharp:"/**\n * Definition for a binary tree node.\n * public class TreeNode {\n * public int val;\n * public TreeNode left;\n * public TreeNode right;\n * public TreeNode(int x) { val = x; }\n * }\n */\npublic class Solution {\n public int LowestCommonAncestor(TreeNode root, int p, int q) {\n // Write your solution here\n return 0;\n }\n}",go:"/**\n * Definition for a binary tree node.\n * type TreeNode struct {\n * Val int\n * Left *TreeNode\n * Right *TreeNode\n * }\n */\nfunc lowestCommonAncestor(root *TreeNode, p int, q int) int {\n // Write your solution here\n return 0\n}"},generateFrames:e=>{let{root:n,p:t,q:r}=e,l=[],{rootId:i,nodes:a}=(0,o.j)(n),d=null,s=null;for(let[e,n]of Object.entries(a))n.val===t&&(d=parseInt(e)),n.val===r&&(s=parseInt(e));let u=[],c={},f=null,h=function(e){let n=arguments.length>1&&void 0!==arguments[1]?arguments[1]:"default",t=arguments.length>2&&void 0!==arguments[2]?arguments[2]:null;return{rootId:i,nodes:JSON.parse(JSON.stringify(a)),activeNodeId:t,visited:[...u],pNodeId:d,qNodeId:s,lcaNodeId:f,dfsPath:[...u],returnedNodes:{...c},currentRecursionNodeId:t,message:e,status:n}};l.push({stepId:"start_dfs",line:1,state:h("Finding LCA of nodes with values ".concat(t," and ").concat(r))});let p=function e(n){if(l.push({stepId:"check_null",line:2,state:h(null===n?"Node is null":"Visiting node ".concat(a[n].val),"checking",n)}),null===n)return l.push({stepId:"return_null",line:2,state:h("Returning null (base case)","default",null)}),null;u.push(n);let o=a[n].val;if(l.push({stepId:"check_target",line:3,state:h("Checking if ".concat(o," equals ").concat(t," or ").concat(r),"checking",n)}),o===t||o===r)return c[n]="self",l.push({stepId:"return_target",line:3,state:h("Found target node ".concat(o,"! Returning this node."),"found",n)}),n;l.push({stepId:"recurse_left",line:4,state:h("Recursing into left subtree of node ".concat(o),"default",n)});let i=e(a[n].leftId);l.push({stepId:"recurse_right",line:5,state:h("Recursing into right subtree of node ".concat(o),"default",n)});let d=e(a[n].rightId);if(l.push({stepId:"check_both",line:6,state:h("At node ".concat(o,": left=").concat(null!==i?a[i].val:"null",", right=").concat(null!==d?a[d].val:"null"),"checking",n)}),null!==i&&null!==d)return f=n,c[n]="both",l.push({stepId:"return_lca",line:6,state:h("Both subtrees returned non-null! Node ".concat(o," is the LCA!"),"found",n)}),n;let s=null!==i?i:d;return null!==s&&(c[n]=null!==i?"left":"right"),l.push({stepId:"return_found",line:7,state:h("Returning ".concat(null!==s?a[s].val:"null"," from node ").concat(o),null!==s?"checking":"default",n)}),s}(i);return null!==p&&l.push({stepId:"final_return",line:8,state:h("LCA found: ".concat(a[p
1].val),"found",p)}),l}}},63969:function(e,n,t){t.d(n,{j:function(){return r}});function r(e){let n=arguments.length>1&&void 0!==arguments[1]?arguments[1]:0,t=arguments.length>2&&void 0!==arguments[2]?arguments[2]:300,r=arguments.length>3&&void 0!==arguments[3]?arguments[3]:40;if(!e||0===e.length||null===e[0])return{rootId:null,nodes:{},nextId:n};let o={},l=n,i={id:l++,val:e[0],leftId:null,rightId:null,x:t,y:r};o[i.id]=i;let a=[{node:i,level:0}],d=1;for(;d<e.length&&a.length>0;){let{node:n,level:t}=a.shift(),r=140/Math.pow(2,t);if(d<e.length){let i=e[d++];if(null!==i){let e={id:l++,val:i,leftId:null,rightId:null,x:n.x-r,y:n.y+80};o[e.id]=e,n.leftId=e.id,a.push({node:e,level:t+1})}}if(d<e.length){let i=e[d++];if(null!==i){let e={id:l++,val:i,leftId:null,rightId:null,x:n.x+r,y:n.y+80};o[e.id]=e,n.rightId=e.id,a.push({node:e,level:t+1})}}}return{rootId:i.id,nodes:o,nextId:l}}},88078:function(e,n,t){t.d(n,{LCABinaryTreeRenderer:function(){return a}});var r=t(57437);t(2265);var o=t(63832),l=t(46387),i=t(19902);let a=e=>{var n,t,a;let{frame:d}=e,{rootId:s,nodes:u,activeNodeId:c,visited:f,pNodeId:h,qNodeId:p,lcaNodeId:g,dfsPath:x,returnedNodes:b,message:v,status:_}=d.state,m=Object.values(u).flatMap(e=>{let n=[];if(null!==e.leftId&&u[e.leftId]){let t=x.includes(e.id)&&x.includes(e.leftId);n.push({id:"".concat(e.id,"-").concat(e.leftId),x1:e.x,y1:e.y,x2:u[e.leftId].x,y2:u[e.leftId].y,isPath:t})}if(null!==e.rightId&&u[e.rightId]){let t=x.includes(e.id)&&x.includes(e.rightId);n.push({id:"".concat(e.id,"-").concat(e.rightId),x1:e.x,y1:e.y,x2:u[e.rightId].x,y2:u[e.rightId].y,isPath:t})}return n}),y=e=>{let n=e===c,t=e===h,r=e===p,o=e===g,l=f.includes(e),i=b[e],a="#27272a",d="#3f3f46",s=2;return(t||r)&&(a="#7c3aed",d="#a78bfa"),o&&"found"===_&&(a="#22c55e",d="#4ade80",s=3),n&&("checking"===_?(a="#f59e0b",d="#fbbf24"):"found"===_?(a="#22c55e",d="#4ade80"):(a="#3b82f6",d="#60a5fa")),!l||n||o||(d="#60a5fa"),!i||n||o||("both"===i?d="#22c55e":"self"===i?d="#a78bfa":"left"!==i&&"right"!==i||(d="#60a5fa")),{bgcolor:a,borderColor:d,borderWidth:s}},N=e=>e===h?"p":e===p?"q":null;return(0,r.jsxs)(o.Z,{sx:{display:"flex",flexDirection:"column",alignItems:"center",gap:3,p:4,width:"100%",height:"100%",position:"relative"},children:[(0,r.jsx)(o.Z,{sx:{minHeight:50,display:"flex",alignItems:"center",justifyContent:"center",maxWidth:600},children:v&&(0,r.jsx)(l.Z,{color:"#a1a1aa",textAlign:"center",variant:"body2",children:v})}),(0,r.jsxs)(o.Z,{sx:{display:"flex",gap:3,flexWrap:"wrap",justifyContent:"center"},children:[(0,r.jsxs)(o.Z,{sx:{display:"flex",alignItems:"center",gap:1},children:[(0,r.jsx)(o.Z,{sx:{width:16,height:16,borderRadius:"50%",bgcolor:"#7c3aed",border:"2px solid #a78bfa"}}),(0,r.jsx)(l.Z,{variant:"caption",color:"#a1a1aa",children:"Target (p/q)"})]}),(0,r.jsxs)(o.Z,{sx:{display:"flex",alignItems:"center",gap:1},children:[(0,r.jsx)(o.Z,{sx:{width:16,height:16,borderRadius:"50%",bgcolor:"#3b82f6",border:"2px solid #60a5fa"}}),(0,r.jsx)(l.Z,{variant:"caption",color:"#a1a1aa",children:"Current Node"})]}),(0,r.jsxs)(o.Z,{sx:{display:"flex",alignItems:"center",gap:1},children:[(0,r.jsx)(o.Z,{sx:{width:16,height:16,borderRadius:"50%",bgcolor:"#22c55e",border:"2px solid #4ade80"}}),(0,r.jsx)(l.Z,{variant:"caption",color:"#a1a1aa",children:"LCA Found"})]}),(0,r.jsxs)(o.Z,{sx:{display:"flex",alignItems:"center",gap:1},children:[(0,r.jsx)(o.Z,{sx:{width:16,height:16,borderRadius:"50%",bgcolor:"#27272a",border:"2px solid #60a5fa"}}),(0,r.jsx)(l.Z,{variant:"caption",color:"#a1a1aa",children:"Visited"})]})]}),(0,r.jsxs)(o.Z,{sx:{display:"flex",gap:3,flexWrap:"wrap",justifyContent:"center"},children:[null!==h&&(0,r.jsxs)(i.Z,{sx:{p:1,px:2,bgcolor:"#18181b",border:"1px solid #7c3aed"},children:[(0,r.jsx)(l.Z,{variant:"caption",color:"#a1a1aa",children:"p"}),(0,r.jsx)(l.Z,{variant:"h6",color:"#a78bfa",children:null===(n=u[h])||void 0===n?void 0:n.val})]}),null!==p&&(0,r.jsxs)(i.Z,{sx:{p:1,px:2,bgcolor:"#18181b",border:"1px solid #7c3aed"},children:[(0,r.jsx)(l.Z,{variant:"caption",color:"#a1a1aa",children:"q"}),(0,r.jsx)(l.Z,{variant:"h6",color:"#a78bfa",children:null===(t=u[p])||void 0===t?void 0:t.val})]}),null!==g&&(0,r.jsxs)(i.Z,{sx:{p:1,px:2,bgcolor:"#18181b",border:"1px solid #22c55e"},children:[(0,r.jsx)(l.Z,{variant:"caption",color:"#a1a1aa",children:"LCA"}),(0,r.jsx)(l.Z,{variant:"h6",color:"#22c55e",children:null===(a=u[g])||void 0===a?void 0:a.val})]}),(0,r.jsxs)(i.Z,{sx:{p:1,px:2,bgcolor:"#18181b",border:"1px solid #3f3f46"},children:[(0,r.jsx)(l.Z,{variant:"caption",color:"#a1a1aa",children:"DFS Path"}),(0,r.jsx)(l.Z,{variant:"body2",color:"#60a5fa",children:x.length>0?x.map(e=>{var n;return null===(n=u[e])||void 0===n?void 0:n.val}).join(" -> "):"-"})]})]}),(0,r.jsxs)(o.Z,{sx:{width:650,height:380,position:"relative"},children:[(0,r.jsx)("svg",{style:{position:"absolute",top:0,left:0,width:"100%",height:"100%",overflow:"visible"},children:m.map(e=>(0,r.jsx)("line",{x1:e.x1,y1:e.y1,x2:e.x2,y2:e.y2,stroke:e.isPath?"#60a5fa":"#3f3f46",strokeWidth:e.isPath?3:2,strokeDasharray:(e.isPath,"none")},e.id))}),Object.values(u).map(e=>{let{bgcolor:n,borderColor:t,borderWidth:i}=y(e.id),a=N(e.id),d=e.id===c;return(0,r.jsxs)(o.Z,{sx:{position:"absolute",left:e.x,top:e.y,transform:"translate(-50%, -50%)",display:"flex",flexDirection:"column",alignItems:"center"},children:[a&&(0,r.jsx)(l.Z,{sx:{position:"absolute",top:-20,color:"#a78bfa",fontWeight:"bold",fontSize:"12px"},children:a}),(0,r.jsx)(o.Z,{sx:{width:44,height:44,borderRadius:"50%",bgcolor:n,border:"".concat(i,"px solid ").concat(t),display:"flex",alignItems:"center",justifyContent:"center",transition:"all 0.3s ease",boxShadow:d?"0 0 15px ".concat(t,"80"):"none",zIndex:2},children:(0,r.jsx)(l.Z,{fontWeight:"bold",color:"#fff",fontSize:"14px",children:e.val})}),b[e.id]&&(0,r.jsx)(l.Z,{sx:{position:"absolute",bottom:-18,color:"both"===b[e.id]?"#22c55e":"self"===b[e.id]?"#a78bfa":"#60a5fa",fontWeight:"bold",fontSize:"10px"},children:"both"===b[e.id]?"LCA":"self"===b[e.id]?"found":"left"
1===b[e.id]?"L":"R"})]},e.id)})]})]})}}}]);
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.