Root Path as DLL

Given a TreeNode pointer and a binary tree, return the root to TreeNode path as a doubly linked list.

The Idea: Begin with a DFS traversal through the tree that collects the path as you traverse along. Once you identify the proper node, break out of the DFS and return the DLL version of that list.

Complexity: O(c*height-tree) for identifying the node within the tree, and then constructing the list out of it. C is just a heavy constant.

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

class BTree:
    def __init__(self):
        self.root = None

    def getRoot(self):
        return self.root

    def add(self, val):
        if(self.root == None):
            self.root = TreeNode(val)
        else:
            self._add(val, self.root)

    def _add(self, val, node):
        if(val < node.val):
            if(node.left != None):
                self._add(val, node.left)
            else:
                node.left = TreeNode(val)
        else:
            if(node.right != None):
                self._add(val, node.right)
            else:
                node.right = TreeNode(val)

    def find(self, val):
        if(self.root != None):
            return self._find(val, self.root)
        else:
            return None

    def _find(self, val, node):
        if(val == node.val):
            return node
        elif(val < node.val and node.left != None):
            self._find(val, node.l)
        elif(val > node.val and node.right != None):
            self._find(val, node.right)

    def deleteTree(self):
        # garbage collector will do this for us.
        self.root = None

    def printTree(self):
        if(self.root != None):
            self._printTree(self.root)

    def _printTree(self, node):
        if(node != None):
            self._printTree(node.left)
            print(str(node.val) + ' ')
            self._printTree(node.right)

#     3
# 0     4
#   2      8
tree = BTree()
tree.add(3)
tree.add(4)
tree.add(0)
tree.add(8)
tree.add(2)
tree.printTree()
print((tree.find(3)).val)
print(tree.find(10))



def treeNodePathtoDLL(root, tree_node_val):
    path = []
    finish = [False]
    def dfs(root):
        if root and not finish[0]:
            path.append(root.val)
            if root.val == tree_node_val:
                finish[0] = True
                return
            else:
                dfs(root.left)
                dfs(root.right)
                if not finish[0]:
                    path.pop()
    dfs(root)
    return DLL(path) if path else None


def printDLL(dll_node, is_front):
    iter = dll_node
    if is_front:
        while iter:
            print('%i -> ' % iter.val, end='')
            iter = iter.next
        print()
    else:
        while iter:
            print('%i <- ' % iter.val, end='')
            iter = iter.prev
        print()


class DLL_node:
    def __init__(self, val):
        self.prev, self.next = None, None
        self.val = val


class DLL:
    def __init__(self, list):
        """
        :param list: construct DLL via list
        """
        self.front = None
        self.tail = None

        for elm in list:
            self.addNode(elm)

    def addNode(self, elm):
        if not self.front:
            self.tail = self.front = DLL_node(elm)
        else:
            tmp = self.tail
            self.tail.next = DLL_node(elm)
            self.tail = self.tail.next
            self.tail.prev = tmp



DLL_t1 = treeNodePathtoDLL(tree.root, 3)
printDLL(DLL_t1.front, True)
printDLL(DLL_t1.tail, False)


DLL_t2 = treeNodePathtoDLL(tree.root, 8)
printDLL(DLL_t2.front, True)
printDLL(DLL_t2.tail, False)


DLL_t3 = treeNodePathtoDLL(tree.root, 2)
printDLL(DLL_t3.front, True)
printDLL(DLL_t3.tail, False)


DLL_t4 = treeNodePathtoDLL(tree.root, 4)
printDLL(DLL_t4.front, True)
printDLL(DLL_t4.tail, False)

DLL_t5 = treeNodePathtoDLL(tree.root, 100)
printDLL(DLL_t5.front, True)
printDLL(DLL_t5.tail, False)