Flatten Binary Tree to Linked List - Depth First Search / Binary Search Tree

Problems
1

https://algo.monster/problems/flatten_binary_tree

2

In pre-order traversal, it is Root - left - right.
In solution 1, why are you adding right first and then the left subtree…?
In the illustrations it is correct, but not reflected in the first solution…?

3

Cuz it uses stack as the container to mimic the behavior of DFS.
And since stack is FILO (first in last out), we actually process the LAST element we have added first as we pop the elements out the stack(left → right). So the left subtrees will be processed first, since its been added last.
command | stack

  1. stack=[] | [(empty)]
  2. stack.append(right) | [right]
  3. stack.append(left) | [right, left]
  4. top = stack.pop() | [right], top = left
4

The binary tree itself is not valid, why this is a binary tree problem?

5

There is a better way to do this. Notice that with a pre-order traversal, you can’t easily recurse and make a list. Pre-order traversal is Node, Left, Right. If you modify the node’s right pointer to point at the next element in the traversal, then you lose access to your right child before you get a chance to visit it…

Notice however that a post-order traversal would make this a lot easier! In post order, we have already visited the children prior to operating on the current node. We could simply keep a global (outside of the recursion) that holds the last node visited, and then set the right child of the current node to point to the global! That would be so much easier!

How can we convert pre-order to post-order? Notice that pre-order traversal is NLR. Reverse the letters and you get the reverse traversal order that is a post-order traversal RLN. Therefore, when processing the current node, the previous processed node comes next in the pre-order traversal.

def flatten_tree(tree: Node) → Node:

next_node = None

def flatten(node):
    nonlocal next_node

    if not node:
        return 

    flatten(node.right)
    flatten(node.left)            

    if next_node:
        node.right = next_node
        node.left = None

    next_node = node

flatten(tree)
return tree
6

Another JS solution, global stack is used to preserve all the right nodes, all nodes in stack also go under dfs and add to the end of the list that build from the original tree.

function flattenTree(tree) {

let rightNodes = []

function dfs(node, stackRightNode){
    if(!node){
        return
    }
    console.log(node)
    
    if(node.right){
    stackRightNode.push(node.right)
    }
    
    node.right = node.left
    node.left = null
    
    dfs(node.right, stackRightNode)
    

    while(stackRightNode.length > 0){
        let right = stackRightNode.pop()
        node.right = dfs(right, stackRightNode)
    }
    
    return node
    
}

return dfs(tree, rightNodes)

}