Jobs

Interviews

Discussions

Binary Tree Upside Down

Medium

8 views

Topics:

TreesRecursion

Given the root of a binary tree, turn the binary tree upside down and return the new root.

You can turn a binary tree upside down with the following steps:

The original left child becomes the new root.
The original root becomes the new right child.
The original right child becomes the new left child.

The mentioned steps are performed in-place.

Example 1:

Input: root = [1,2,3,4,5]
Output: [4,5,2,null,null,3,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Constraints:

The number of nodes in the tree will be in the range [0, 10].
1 <= Node.val <= 10
Each node has either 0 or 2 children.

Try coding it in LeetCode

Binary Tree Upside Down

Medium

8 views

Topics:

TreesRecursion

Given the root of a binary tree, turn the binary tree upside down and return the new root.

You can turn a binary tree upside down with the following steps:

The original left child becomes the new root.
The original root becomes the new right child.
The original right child becomes the new left child.

The mentioned steps are performed in-place.

Example 1:

Input: root = [1,2,3,4,5]
Output: [4,5,2,null,null,3,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Constraints:

The number of nodes in the tree will be in the range [0, 10].
1 <= Node.val <= 10
Each node has either 0 or 2 children.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the tree be empty, and if so, what should I return?
Are the node values unique, or can there be duplicates?
Is it guaranteed that all right nodes are either leaf nodes with a null left child or have a sibling (a left node)?
Can you provide an example input and its corresponding expected upside-down tree output?
Are there any memory constraints I should be aware of, considering I'll be manipulating the tree structure?

Brute Force Solution

Approach

The brute force approach to flipping a binary tree upside down involves exploring all possible reconfigurations by rearranging the connections between the nodes. We essentially examine every possible upside-down version of the tree.

Here's how the algorithm would work step-by-step:

Start at the very bottom left node of the tree.
Make this bottom left node the new root of the upside-down tree.
Now, look at the parent of this node; it becomes the left child of the new root.
Next, look at the right sibling (if it exists) of the original root's left child; it becomes the right child of the new root.
Move up the tree, applying the same transformation to each parent-child relationship, effectively swapping left and right children and attaching the original parent to the new child.
Repeat until the original root becomes the new rightmost node in the upside-down tree.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def upside_down_binary_tree_brute_force(root):
    current_node = root
    previous_right = None
    parent = None

    while current_node:
        # Store the left node, since we'll change its reference
        next_left = current_node.left

        # The new root's left child becomes the original root
        current_node.left = previous_right

        # The new root's right child is the original root's parent
        previous_right = current_node.right
        current_node.right = parent

        parent = current_node
        current_node = next_left

    return parent

Big(O) Analysis

Time Complexity

O(n) – The provided algorithm traverses the binary tree once, starting from the bottom-left node and working its way up to the root. Each node is visited and its connections are rearranged a constant number of times. Because the work done at each node is constant and we visit each of the n nodes in the tree, the time complexity is directly proportional to the number of nodes.

Space Complexity

O(1) – The provided plain English explanation describes an iterative process of re-arranging nodes in place. It doesn't mention any explicit auxiliary data structures like arrays, hash maps, or lists being created. Although the process involves manipulating parent-child relationships, this happens directly on the existing tree structure. Therefore, the auxiliary space used remains constant regardless of the number of nodes (N) in the tree, resulting in a space complexity of O(1).

Optimal Solution

Approach

The core idea is to repeatedly transform the tree from the bottom-left up. We iteratively rewire the nodes to achieve the upside-down transformation. This is done by updating the left, right, and parent pointers of the nodes.

Here's how the algorithm would work step-by-step:

Start at the leftmost node at the bottom level of the tree. This will become the new root.
Make the original root of the subtree the new left child of the new root.
Make the original right child of the subtree the new right child of the new root.
Sever the original left and right child connections from what was the bottom-left node.
Move one level up and repeat the process until the original root is processed.
The original root will become the new left child of the node directly above it. Its right child becomes its right child.
Finally, the original root now must have its left and right pointers set to nothing so as not to disturb the tree structure.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def upside_down_binary_tree(root):
    current_node = root
    previous_right_node = None
    parent_node = None

    while current_node:
        # Store the left and right nodes
        left_node = current_node.left
        right_node = current_node.right

        # The leftmost node becomes the new root
        current_node.left = previous_right_node

        # The current node becomes the left child of the node above
        current_node.right = parent_node

        # Update variables to move up one level
        previous_right_node = right_node
        parent_node = current_node
        current_node = left_node

    return parent_node

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree exactly once. Starting from the bottom-left, the algorithm rewires the tree by adjusting the left, right, and parent pointers of each node. The number of operations is directly proportional to the number of nodes (n) in the tree since each node is processed a fixed number of times. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The upsideDownBinaryTree transformation described does not utilize any auxiliary data structures such as arrays, hash maps, or queues. The operations involve re-wiring pointers in-place. Consequently, the space required beyond the input tree itself is constant. Thus, the auxiliary space complexity is O(1), irrespective of the number of nodes N in the binary tree.

Edge Cases

Case	How to Handle
Null root input	Return null immediately; an empty tree upside-down is still empty.
Single node tree	Return the original root node as it is already 'upside down'.
Tree with only left children (no right children)	The algorithm should correctly re-wire the left-leaning tree into its upside-down equivalent, handling null right children gracefully.
Perfectly balanced binary tree	The algorithm must correctly invert the structure while maintaining the parent-child relationships in the correct inverted order.
Skewed tree (left or right)	Ensure algorithm transforms the skewed tree accurately without losing any nodes and maintaining the new structure's integrity.
Tree with duplicate values	Duplicate values do not inherently affect the algorithm's logic as it focuses on structural transformation, not value uniqueness.
Very large tree (potential stack overflow with recursion)	Consider an iterative solution to avoid potential stack overflow issues in cases of extremely deep trees.
Tree violating the sibling constraint (right node not a leaf or without a sibling)	State in the prompt that we assume the input tree follows the constraint, so it's not strictly an 'edge' case that needs specific handling, just valid input.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the tree be empty, and if so, what should I return?
Are the node values unique, or can there be duplicates?
Is it guaranteed that all right nodes are either leaf nodes with a null left child or have a sibling (a left node)?
Can you provide an example input and its corresponding expected upside-down tree output?
Are there any memory constraints I should be aware of, considering I'll be manipulating the tree structure?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very bottom left node of the tree.
Make this bottom left node the new root of the upside-down tree.
Now, look at the parent of this node; it becomes the left child of the new root.
Next, look at the right sibling (if it exists) of the original root's left child; it becomes the right child of the new root.
Move up the tree, applying the same transformation to each parent-child relationship, effectively swapping left and right children and attaching the original parent to the new child.
Repeat until the original root becomes the new rightmost node in the upside-down tree.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def upside_down_binary_tree_brute_force(root):
    current_node = root
    previous_right = None
    parent = None

    while current_node:
        # Store the left node, since we'll change its reference
        next_left = current_node.left

        # The new root's left child becomes the original root
        current_node.left = previous_right

        # The new root's right child is the original root's parent
        previous_right = current_node.right
        current_node.right = parent

        parent = current_node
        current_node = next_left

    return parent

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the leftmost node at the bottom level of the tree. This will become the new root.
Make the original root of the subtree the new left child of the new root.
Make the original right child of the subtree the new right child of the new root.
Sever the original left and right child connections from what was the bottom-left node.
Move one level up and repeat the process until the original root is processed.
The original root will become the new left child of the node directly above it. Its right child becomes its right child.
Finally, the original root now must have its left and right pointers set to nothing so as not to disturb the tree structure.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def upside_down_binary_tree(root):
    current_node = root
    previous_right_node = None
    parent_node = None

    while current_node:
        # Store the left and right nodes
        left_node = current_node.left
        right_node = current_node.right

        # The leftmost node becomes the new root
        current_node.left = previous_right_node

        # The current node becomes the left child of the node above
        current_node.right = parent_node

        # Update variables to move up one level
        previous_right_node = right_node
        parent_node = current_node
        current_node = left_node

    return parent_node

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root input	Return null immediately; an empty tree upside-down is still empty.
Single node tree	Return the original root node as it is already 'upside down'.
Tree with only left children (no right children)	The algorithm should correctly re-wire the left-leaning tree into its upside-down equivalent, handling null right children gracefully.
Perfectly balanced binary tree	The algorithm must correctly invert the structure while maintaining the parent-child relationships in the correct inverted order.
Skewed tree (left or right)	Ensure algorithm transforms the skewed tree accurately without losing any nodes and maintaining the new structure's integrity.
Tree with duplicate values	Duplicate values do not inherently affect the algorithm's logic as it focuses on structural transformation, not value uniqueness.
Very large tree (potential stack overflow with recursion)	Consider an iterative solution to avoid potential stack overflow issues in cases of extremely deep trees.
Tree violating the sibling constraint (right node not a leaf or without a sibling)	State in the prompt that we assume the input tree follows the constraint, so it's not strictly an 'edge' case that needs specific handling, just valid input.