Posts

Showing posts with the label Smallest Subtree with all the Deepest Nodes

Smallest Subtree with all the Deepest Nodes

Given the   root   of a binary tree, the depth of each node is   the shortest distance to the root . Return  the smallest subtree  such that it contains  all the deepest nodes  in the original tree. A node is called  the deepest  if it has the largest depth possible among any node in the entire tree. The  subtree  of a node is tree consisting of that node, plus the set of all descendants of that node. Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4] Output: [2,7,4] Example 2: Input: root = [1] Output: [1] Explanation: The root is the deepest node in the tree. Example 3: Input: root = [0,1,3,null,2] Output: [2] Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.   Constraints: The number of nodes in the tree will be in the range  [1, 500] . 0...