NUHMAN.com

Introduction

LeetCode 114: Flatten Binary Tree to Linked List asks us to flatten a binary tree into a linked list in place. The flattened tree should follow the same structure as a linked list, where the left child of each node is nil and the right child points to the next node in the preorder traversal of the binary tree.

Problem Statement

Given the root of a binary tree, flatten it into a linked list in-place such that:

1. The left child of every node should be set to nil.
2. The right child of each node should point to the next node in the preorder traversal of the tree.

Example:

go

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

Approach:

Using Depth-First Search (DFS)

We can solve this problem using a DFS traversal to flatten the tree. The idea is to traverse the tree in a preorder fashion (visit the root, then the left subtree, and finally the right subtree). During this traversal, we keep track of the previous node in the traversal and set the left child to nil and the right child to the next node in the preorder sequence.

1. DFS Algorithm:

• Start with the root node.
• For each node, recursively flatten the left and right subtrees.
• Keep track of the previous node visited in the preorder traversal.
• Set the left child to nil and the right child to the next node in the preorder traversal.

1. Steps:

• Traverse the tree starting from the root using DFS.
• Modify the left child of each node to be nil.
• Attach the flattened right subtree to the right child of the current node.

1. In-Place Transformation:

• Since the problem asks for an in-place transformation, we must modify the tree directly without using any additional data structures like a new tree or list.

Go Implementation

Solution Using DFS

go

package main

// TreeNode represents a node in the binary tree.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// flatten flattens the binary tree into a linked list in-place.
func flatten(root *TreeNode) {
    if root == nil {
        return
    }

    // Recursively flatten the left and right subtrees.
    flatten(root.Left)
    flatten(root.Right)

    // Store the right subtree (which will be flattened).
    rightSubtree := root.Right

    // Set the left child to nil (as required).
    root.Right = root.Left
    root.Left = nil

    // Find the rightmost node of the current node's right subtree.
    curr := root
    for curr.Right != nil {
        curr = curr.Right
    }

    // Attach the previously stored right subtree to the rightmost node.
    curr.Right = rightSubtree
}

Explanation:

1. TreeNode Structure:

• The TreeNode struct represents a node in the binary tree, with an integer value (Val) and pointers to its left (Left) and right (Right) children.

1. flatten Function:

• This function is the main entry point and recursively flattens the tree.
• It first checks if the root is nil (base case). If it is, it returns.
• The function then recursively flattens the left and right subtrees by calling flatten on both root.Left and root.Right.
• After the recursion, it stores the right subtree (rightSubtree), sets root.Right to the flattened left subtree, and sets root.Left to nil (since we want a linked list).
• Finally, it traverses to the rightmost node of the current right subtree and attaches the previously stored right subtree to it.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(h)

Where:

• n is the number of nodes in the binary tree.
• h is the height of the tree.

Time Complexity:

• The time complexity is O(n) because we visit each node in the tree exactly once during the DFS traversal.

Space Complexity:

• The space complexity is O(h) due to the recursion stack used in DFS. In the worst case, the height of the tree could be n (if the tree is unbalanced), and in the best case, the height is log n (if the tree is balanced).

Edge Cases

1. Empty Tree:

• Input: root = nil
• Output: []
• Explanation: An empty tree remains unchanged.

1. Single Node Tree:

• Input: root = [1]
• Output: [1]
• Explanation: A tree with a single node is already flattened.

1. Already Flattened Tree:

• Input: root = [1, null, 2, null, 3]
• Output: [1, null, 2, null, 3]
• Explanation: A tree that's already flattened should not be changed.

1. Unbalanced Tree:

• Input: root = [1, 2, null, 3, null, 4]
• Output: [1, null, 2, null, 3, null, 4]
• Explanation: Even if the tree is unbalanced, it should still be flattened into a linked list.

Conclusion

LeetCode 114: Flatten Binary Tree to Linked List is an interesting problem that challenges us to manipulate the binary tree structure in place. By using DFS and recursive traversal, we can flatten the tree while adhering to the problem’s constraints. This solution runs in O(n) time and uses O(h) space, where n is the number of nodes in the tree and h is the height of the tree.