Tree node definition 1 2 3 4 5 class Node : def __init__ (self, val ): self.val = val self.left = None self.right = None
To build the tree nodes:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 root = Node(0 ) n1 = Node(1 ) n2 = Node(2 ) root.left = n1 root.right = n2 n3 = Node(3 ) n4 = Node(4 ) n1.left = n3 n1.right = n4 n5 = Node(5 ) n6 = Node(6 ) n2.left = n5 n2.right = n6 n7 = Node(7 ) n8 = Node(8 ) n3.left = n7 n3.right = n8
The tree looks like below:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 0 / \ 1 2 / \ / \ 3 4 5 6 / \ 7 8 class Node : def __init__ (self, val ): self.val = val self.left = None self.right = None ``` To build the tree nodes: ```python root = Node(0 ) n1 = Node(1 ) n2 = Node(2 ) root.left = n1 root.right = n2 n3 = Node(3 ) n4 = Node(4 ) n1.left = n3 n1.right = n4 n5 = Node(5 ) n6 = Node(6 ) n2.left = n5 n2.right = n6 n7 = Node(7 ) n8 = Node(8 ) n3.left = n7 n3.right = n8
The tree looks like below:
1 2 3 4 5 6 7 0 / \ 1 2 / \ / \ 3 4 5 6 / \ 7 8
Pre-order traversal 1 2 3 4 5 6 7 8 9 10 11 12 def pre_order_traverse (node ): if node == None : return print (f"{node.val} " , end="" ) pre_order_traverse(node.left) pre_order_traverse(node.right) pre_order_traverse(root) print ()
In-order traversal 1 2 3 4 5 6 7 8 9 10 11 12 def in_order_traverse (node ): if node == None : return in_order_traverse(node.left) print (f"{node.val} " , end="" ) in_order_traverse(node.right) in_order_traverse(root) print ()
Post-order traversal 1 2 3 4 5 6 7 8 9 10 11 12 def post_order_traverse (node ): if node == None : return post_order_traverse(node.left) post_order_traverse(node.right) print (f"{node.val} " , end="" ) post_order_traverse(root) print ()
Get tree size 1 2 3 4 5 6 7 8 9 10 def size (node ): if node == None : return 0 return size(node.left) + 1 + size(node.right) print (f"size: {size(root)} " )
Get tree depth 1 2 3 4 5 6 7 8 9 10 def depth (node ): if node == None : return 0 return max (depth(node.left), depth(node.right)) + 1 print (f"depth: {depth(root)} " )
Print all the paths in the tree 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 def printPaths (node, path ): if node == None : return path.append(node.val) if node.left == None and node.right == None : print ("path : " , end="" ) for n in path: print (f"{n} " , end="" ) print () else : printPaths(node.left, path) printPaths(node.right, path) path.pop() printPaths(root, list ())
Check if path exists for target sum 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def hasPathSum (node, sum ): if node == None : return sum == 0 sum -= node.val return hasPathSum(node.left, sum ) or hasPathSum(node.right, sum ) print (hasPathSum(root, 7 ))print (hasPathSum(root, 12 ))print (hasPathSum(root, 10 ))