ConvertBST2DLL.md

Analysis and Example

                         N0
                    /         \
                   N1         N2
               /       \
              N3(node)  N4
              ^                     ... DOING: DFS to HIT the 1st None Node to get 1) head 2) last
              |
         head, last

    *** Result:
         N3
         ^
         |
    head, last

         -------------------------------------------------------------

                      N0
                 /         \
                N1(node)    N2
              // \                  ... DOING: Iter 1 connecting LEFT: 1) last.right = node; 2) node.left = last
              N3 N4
              ^
              |
      head, last

    *** Result:
         N3    <-->    N1
         ^             ^
         |             |
    head, last       node

         -------------------------------------------------------------


                      N0
                 /         \
                N1(node)   N2
                ^
                |                   ... DOING: 3) last = node;  Taking recording of the trace.
               last
              //  \
              N3  N4
              ^
              |
            head

    *** Result:
         N3    <-->    N1
         ^             ^
         |             |
       head          node
                       ^
                       |
                      last

         -------------------------------------------------------------

                      N0
                 /         \
                N1         N2
                ^
                |
               last
              //  \\
              N3   N4(node)         ... DOING: 4) connecting RIGHT: 1) last.right = node; 2) node.left = last
              ^
              |
            head

    *** Result:
         N3    <-->    N1    <-->    N4
         ^             ^             ^
         |             |             |
       head          last          node

         -------------------------------------------------------------

                      N0
                 /         \
                N1         N2
              //  \\
              N3   N4(node)
              ^    ^
              |    |                ... DOING: 5) last = node; Note: taking recording of the trace.
            head last

    *** Result:
         N3    <-->    N1    <-->    N4
         ^                           ^
         |                           |
       head                        node
                                     ^
                                     |
                                    last

         -------------------------------------------------------------

                     N0 (node)      ... DOING: Iter 2
                 /         \
                N1         N2
              //  \\
              N3   N4
              ^    ^
              |    |
            head last

    *** Result:
         N3    <-->    N1    <-->    N4
         ^                           ^
         |                           |
       head                        node
                                     ^
                                     |
                                    last

         -------------------------------------------------------------

                      N0 (node)     ... DOING: Iter 2 connecting LEFT: 1) last.right = node; 2) node.left = last
                 /      //   \
                N1    //     N2
              //  \\ //
              N3   N4
              ^    ^
              |    |
            head last

    *** Result:
         N3    <-->    N1    <-->    N4    <-->    N0
         ^                           ^             ^
         |                           |             |
       head                        last          node

         -------------------------------------------------------------

                         N0 (node)
                          ^
                          |
                         last       ... DOING: 3) last = node;  Taking recording of the trace.
                 /      //      \
                N1    //         N2
              //  \\ //
              N3   N4
              ^
              |
            head

    *** Result:
         N3    <-->    N1    <-->    N4    <-->    N0
         ^                                         ^
         |                                         |
       head                                      node
                                                   ^
                                                   |
                                                  last

         -------------------------------------------------------------

                         N0
                         ^
                         |
                        last
                 /      //  \\      ... DOING: 4) connecting RIGHT: 1) last.right = node; 2) node.left = last
                N1    //     N2 (node)
              //  \\ //
              N3   N4
              ^
              |
            head


    *** Result:
         N3    <-->    N1    <-->    N4    <-->    N0    <-->    N2
         ^                                         ^             ^
         |                                         |             |
       head                                      last          node

         -------------------------------------------------------------

                         N0
                 /      //  \\
                N1    //     N2 (node)   ... In-order Traversal Terminate here since Node2 has no left or right nodes
              //  \\ //      ^
              N3   N4        |
              ^             last
              |
            head

    *** Result:
         N3    <-->    N1    <-->    N4    <-->    N0    <-->    N2
         ^                                                       ^
         |                                                       |
       head                                                    node
                                                                 ^
                                                                 |
                                                                last

         -------------------------------------------------------------

    So, Final result is
        N3    <-->    N1    <-->    N4    <-->    N0    <-->    N2
        ^                                                       ^
        |                                                       |
        head                                                   last

Code

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

class Solution:
  def ConvertBST2DLL(self, root):
    """
    input:
      root, type: Node
    return:
      head of doubled linked list, type: Node
    """

    def helper(node):
      """
      recursion function to do in-order traversal
      """
      nonlocal last, head

      if node:
        # left
        helper(node.left)  # dfs ... until not None node, i.e., left-most

        # node
        if last:
          # link the previous node (last)
          # with the current one (node)
          last.right = node
          node.left = last
        else:
          # keep the smallest node
          # to close DLL later on
          head = node

        last = node
        # right
        helper(node.right)

    if not root:
      return None

    # the smallest (head) and the largest (last) nodes
    head, last = None, None
    helper(root)
    return head

Time complexity

O(N), since we need to traverse all nodes and each node takes O(1) time to connect.

Space complexity

O(N), since the BST height of a recursion call takes at most N depth, the best case happens when it is balanced, i.e., O(logN)