Comment on page

# 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
if(self.root == None):
self.root = TreeNode(val)
else:
if(val < node.val):
if(node.left != None):
else:
node.left = TreeNode(val)
else:
if(node.right != None):
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.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:
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)