Is Change the Root of a Binary Tree easy or hard?

Change the Root of a Binary Tree is rated Medium difficulty on LeetCode. The main challenge is correctly updating parent, left, and right pointers without creating cycles or losing subtrees. Once the pointer reversal pattern is understood, the implementation becomes straightforward.

Change the Root of a Binary Tree Python/Java solution

Most solutions implement an iterative traversal from the leaf to the root and update pointers during the walk. Python, Java, C++, and JavaScript implementations follow the same idea: reverse parent-child links step by step while maintaining valid left and right child references.

How to solve Change the Root of a Binary Tree in O(n)?

Start from the target leaf and move upward using the parent pointer. At each step, detach the node from its parent and make the parent a child of the current node while adjusting left and right pointers. This effectively reverses the path from the leaf to the root and produces the new root in linear time.

What is the best approach for Change the Root of a Binary Tree?

The best approach is in-place pointer reversal along the path from the given leaf to the original root. Traverse upward using parent pointers and reverse the relationships so the parent becomes a child of the current node. Each node on the path is processed once, giving O(n) time and O(1) extra space.

Is Change the Root of a Binary Tree asked at Google/Amazon/Meta?

Tree pointer manipulation and re-rooting problems appear in interviews at companies like Google, Amazon, and Meta. Variants that require modifying parent-child relationships or restructuring trees are common in senior-level coding rounds focused on data structures.

What data structure is used in Change the Root of a Binary Tree?

The problem uses a binary tree where each node contains left, right, and parent pointers. The solution relies on tree traversal and pointer manipulation, often implemented using a depth-first style upward traversal through parent links.

What is the time complexity of Change the Root of a Binary Tree?

The time complexity is O(n) in the worst case, where n is the number of nodes in the tree. Only the nodes along the path from the leaf to the root are modified, which is bounded by the tree height. Space complexity can be O(1) with an in-place approach or O(n) if the path is stored in an auxiliary list.

Description Hints 2 Solution Video 31:16

1666. Change the Root of a Binary Tree

Medium74.4% acceptance1 companyPremium elsewhere, free here

Given the root of a binary tree and a leaf node, reroot the tree so that the leaf is the new root.

You can reroot the tree with the following steps for each node cur on the path starting from the leaf up to the root excluding the root:

If cur has a left child, then that child becomes cur's right child.
cur's original parent becomes cur's left child. Note that in this process the original parent's pointer to cur becomes null, making it have at most one child.

Return the new root of the rerooted tree.

Note: Ensure that your solution sets the Node.parent pointers correctly after rerooting or you will receive "Wrong Answer".

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7
Output: [7,2,null,5,4,3,6,null,null,null,1,null,null,0,8]

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 0
Output: [0,1,null,3,8,5,null,null,null,6,2,null,null,7,4]

Constraints:

The number of nodes in the tree is in the range [2, 100].
-10⁹ <= Node.val <= 10⁹
All Node.val are unique.
leaf exist in the tree.

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Start traversing from the leaf. Always go up till you reach the root.

Hint 2

Change pointers as asked, make the current node's parent its left child, and make the left child the right one if needed.

31:16

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[3,5,1,6,2,0,8,null,null,7,4]
7

Input

[3,5,1,6,2,0,8,null,null,7,4]
0

Your code is saved on this device.Solution