You need to login before you can make any post submission.
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
def print_inorder(root):
if root:
# First recur on left child
print_inorder(root.left)
# then print the data of node
print(root.val, end=" ")
# now recur on right child
print_inorder(root.right)
print("Example:- Binary Tree")
# Root
root = Node(50)
# 1st Level
root.left = Node(17)
root.right = Node(72)
# 2nd Level
root.left.left = Node(12)
root.left.right = Node(23)
root.right.left = Node(54)
root.right.right = Node(76)
# 3rd Level
root.left.left.left = Node(9)
root.left.left.right = Node(14)
root.left.right.right = Node(19)
root.right.left.right = Node(67)
# Print the tree in inorder
print_inorder(root)
print()
Output:
Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways.
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def inorder(root):
if root:
inorder(root.left)
print(root.val, end=" ")
inorder(root.right)
def preorder(root):
if root:
print(root.val, end=" ")
preorder(root.left)
preorder(root.right)
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.val, end=" ")
# Root
root = Node(50)
# 1st Level
root.left = Node(17)
root.right = Node(72)
# 2nd Level
root.left.left = Node(12)
root.left.right = Node(23)
root.right.left = Node(54)
root.right.right = Node(76)
# 3rd Level
root.left.left.left = Node(9)
root.left.left.right = Node(14)
root.left.right.right = Node(19)
root.right.left.right = Node(67)
# Print the tree traversals
print("Inorder Traversal:")
inorder(root)
print("\n\nPreorder Traversal:")
preorder(root)
print("\n\nPostorder Traversal:")
postorder(root)
print()
Output:
Level order traversal of a tree is breadth first traversal for the tree.
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
def level_order_traversal(root):
# (1) If root is None, then return.
if root is None:
return
# (2) Create an empty queue.
queue = []
# (3) Enqueue root to queue.
queue.append(root)
# (4) while queue is not empty.
while(queue):
# Dequeue the temp_node from queue.
temp_node = queue.pop(0)
# Print temp_node.val
print(temp_node.val, end=" ")
# If temp_node's left exists: enqueue left to queue.
if (temp_node.left):
queue.append(temp_node.left)
# And if right exists: enqueue right also to queue.
if (temp_node.right):
queue.append(temp_node.right)
# Root
root = Node(50)
# 1st Level
root.left = Node(17)
root.right = Node(72)
# 2nd Level
root.left.left = Node(12)
root.left.right = Node(23)
root.right.left = Node(54)
root.right.right = Node(76)
# 3rd Level
root.left.left.left = Node(9)
root.left.left.right = Node(14)
root.left.right.right = Node(19)
root.right.left.right = Node(67)
print("Level Order Traversal:")
level_order_traversal(root)
print()
Output:
There are many tree questions that can be solved using any of the above four traversals.
import sys
INT_MIN = -sys.maxsize-1
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
# Computes the number of nodes in tree
def size(root):
if root is None:
return 0
else:
return (1 + size(root.left) + size(root.right))
# Computes the height of tree
def height(root):
if root is None:
return 0
else :
return (1 + max(height(root.left), height(root.right)))
# Computes the number of nodes in tree
def maximum(root):
if root is None:
return INT_MIN
else:
return max(root.val, maximum(root.left), maximum(root.right))
# Root
root = Node(50)
# 1st Level
root.left = Node(17)
root.right = Node(72)
# 2nd Level
root.left.left = Node(12)
root.left.right = Node(23)
root.right.left = Node(54)
root.right.right = Node(76)
# 3rd Level
root.left.left.left = Node(9)
root.left.left.right = Node(14)
root.left.right.right = Node(19)
root.right.left.right = Node(67)
print("Size of Tree: {}".format(size(root)))
print("Height of Tree: {}".format(height(root)))
print("Max of Tree: {}".format(maximum(root)))
Output:
import sys
INT_MIN = -sys.maxsize-1
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
def height(root, max_diam):
if root is None:
return 0
else :
# Get the height of left and right nodes of the current_node
left_height = height(root.left, max_diam)
right_height = height(root.right, max_diam)
# Get the diameter at current_node = 1 + left_height + right_height
# Update the max_diam[0] if current_diam > max_diam[0]
current_diam = 1 + left_height + right_height
max_diam[0] = max(max_diam[0], current_diam)
# return the height of the current_node
return (1 + max(left_height, right_height))
def diameter(root):
if root is None:
return 0
max_diam = [INT_MIN] # This will store the final answer
height(root, max_diam)
return max_diam[0]
# Root
root = Node(13)
# 1st Level
root.left = Node(7)
root.right = Node(2)
# 2nd Level
root.left.left = Node(19)
root.left.right = Node(25)
# 3rd Level
root.left.left.left = Node(11)
root.left.left.right = Node(28)
root.left.right.right = Node(5)
# 4th Level
root.left.left.right.left = Node(35)
root.left.right.right.left = Node(7)
root.left.right.right.right = Node(9)
# 5th Level
root.left.left.right.left.right = Node(26)
root.left.right.right.right.left = Node(17)
print("Diameter of Tree: {}".format(diameter(root)))
Output:
Width of a tree is maximum of widths of all levels.
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
def max_width_binary_tree(root):
# (1) If root is None, then return 0.
if root is None:
return 0
# (2) Create an empty queue and max_width=0.
queue = []
max_width = 0
# (3) Enqueue root to queue.
queue.append(root)
# (4) While queue is not empty.
while(queue):
# Get the current_count and update max_width if it is greater.
current_count = len(queue)
max_width = max(max_width, current_count)
# Dequeue all the nodes instead of one. So, while current_count > 0.
while(current_count > 0):
# Dequeue the temp_node from queue.
temp_node = queue.pop(0)
# If temp_node's left exists: enqueue left to queue.
if (temp_node.left):
queue.append(temp_node.left)
# And if right exists: enqueue right also to queue.
if (temp_node.right):
queue.append(temp_node.right)
current_count -= 1
return max_width
# Root
root = Node(1)
# 1st Level
root.left = Node(2)
root.right = Node(3)
# 2nd Level
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(8)
# 3rd Level
root.right.right.left = Node(6)
root.right.right.right = Node(7)
print("Maximum Width = {}".format(max_width_binary_tree(root)))
Output:
Print all the tree elements when seen from left side.
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
def left_view_binary_tree(root):
# (1) If root is None, then return.
if root is None:
return
# (2) Create an empty queue.
queue = []
# (3) Enqueue root to queue.
queue.append(root)
# (4) While queue is not empty.
while(queue):
# Get the current_count.
current_count = len(queue)
# Flag to know if first element in this level is printed.
printed = False
# Dequeue all the nodes instead of one. So, while current_count > 0.
while(current_count > 0):
# Dequeue the temp_node from queue.
temp_node = queue.pop(0)
# Print the first element in this level if it is not printed.
if(not printed):
print(temp_node.val, end=" ")
printed = True
# If temp_node's left exists: enqueue left to queue.
if (temp_node.left):
queue.append(temp_node.left)
# And if right exists: enqueue right also to queue.
if (temp_node.right):
queue.append(temp_node.right)
current_count -= 1
# Root
root = Node(4)
# 1st Level
root.left = Node(5)
root.right = Node(2)
# 2nd Level
root.right.left = Node(3)
root.right.right = Node(1)
# 3rd Level
root.right.left.left = Node(6)
root.right.left.right = Node(7)
print("Left View of Binary Tree: ")
left_view_binary_tree(root)
print()
Output:
Given a root of a tree, and an integer k. Print all the nodes which are at k distance from root.
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def print_nodes_at_k_distance(root, k):
if root is None:
return
if k==0:
print(root.val, end=" ")
else:
print_nodes_at_k_distance(root.left, k-1)
print_nodes_at_k_distance(root.right, k-1)
# Root
root = Node(50)
# 1st Level
root.left = Node(17)
root.right = Node(72)
# 2nd Level
root.left.left = Node(12)
root.left.right = Node(23)
root.right.left = Node(54)
root.right.right = Node(76)
# 3rd Level
root.left.left.left = Node(9)
root.left.left.right = Node(14)
root.left.right.right = Node(19)
root.right.left.right = Node(67)
print("Nodes at distance of k=2:")
print_nodes_at_k_distance(root, 2)
print()
Output:
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def are_identical(root1, root2):
# If both are NULL, then True.
if root1 is None and root2 is None:
return True
# If one is None and other not None, then False.
if root1 is None or root2 is None:
return False
# Check if the val of both roots is same and left subtree and right subtree are are_identical.
return (root1.val==root2.val and
are_identical(root1.left, root2.left) and
are_identical(root1.right, root2.right))
def is_subtree(S, T):
# If S is None, always subtree.
if S is None:
return True
# If S is not None and T is none, not a subtree.
if T is None:
return False
# If both are identical return True.
if are_identical(S, T):
return True
else:
# Check if S is subtree of T.left or T.right
return is_subtree(S, T.left) or is_subtree(S, T.right)
# Tree T
T = Node(26)
T.left = Node(10)
T.right = Node(3)
T.left.left = Node(4)
T.left.right = Node(6)
T.right.right = Node(3)
T.left.left.right = Node(30)
# Tree S
S = Node(10)
S.left = Node(4)
S.right = Node(6)
S.left.right = Node(30)
print("Example-1: Is Tree S subtree of Tree T ?: {}".format(is_subtree(S, T)))
# Tree S
S = Node(4)
S.right = Node(30)
print("Example-2: Is Tree S subtree of Tree T ?: {}".format(is_subtree(S, T)))
# Tree S
S = Node(4)
S.right = Node(15)
print("Example-3: Is Tree S subtree of Tree T ?: {}".format(is_subtree(S, T)))
Output:
Write a function to connect all the adjacent nodes at the same level in a binary tree.
Initially, all the nextRight pointers point to garbage values, the function should set these pointers to point next right for each node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.nextright = None
def connect_nodes_at_same_level(root):
# (1) If root is None, then return.
if root is None:
return
# (2) Create an empty queue.
queue = []
# (3) Enqueue root to queue.
queue.append(root)
# (4) While queue is not empty.
while(queue):
# Get the current_count.
current_count = len(queue)
# Dequeue all the nodes instead of one. So, while current_count > 0.
while(current_count > 0):
# Dequeue the temp_node from queue.
temp_node = queue.pop(0)
print("{}--->".format(temp_node.val), end="")
# Set the next_right and consider that at every level
# the last element will not point to any other node as the front will be empty.
if(current_count > 1):
temp_node.nextright = queue[0]
else:
temp_node.nextright = None
print("None")
# If temp_node's left exists: enqueue left to queue.
if (temp_node.left):
queue.append(temp_node.left)
# And if right exists: enqueue right also to queue.
if (temp_node.right):
queue.append(temp_node.right)
current_count -= 1
# Root
root = Node(50)
# 1st Level
root.left = Node(17)
root.right = Node(72)
# 2nd Level
root.left.left = Node(12)
root.left.right = Node(23)
root.right.left = Node(54)
root.right.right = Node(76)
# 3rd Level
root.left.left.left = Node(9)
root.left.left.right = Node(14)
root.left.right.right = Node(19)
root.right.left.right = Node(67)
# Call Function
connect_nodes_at_same_level(root)
Output:
Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree.
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def print_ancestors(root, k):
# If root is None return False.
if root is None:
return False
# If root.val is given_node then return True.
if root.val == k:
return True
# Print the root.data if any of root.left or root.right contains the given_node and return True.
if(print_ancestors(root.left, k) or print_ancestors(root.right, k)):
print(root.val, end=" ")
return True
# If given_node not in tree, return False
return False
# Root
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.left.left = Node(7)
print("Ancestors of given_node k=7:")
print_ancestors(root, 7)
print()
print("Ancestors of given_node k=3:")
print_ancestors(root, 3)
print()
Need to do the inorder traversal without using recursion methodology.
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def inorder_without_recursion(root):
current = root
stack = []
while(current is not None or len(stack) > 0):
# Reach the left most Node of the current Node
while (current is not None):
# Place pointer to a tree node on the stack before traversing the node's left subtree
stack.append(current)
current = current.left
# Current must be NULL at this point
current = stack.pop()
print(current.val, end=" ")
# We have visited the node and its left subtree. Now, it's right subtree's turn
current = current.right
print()
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
inorder_without_recursion(root)
Output:
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def morris_inorder_traversal(root):
current = root
while(current is not None):
if current.left is None:
print(current.val, end=" ")
current = current.right
else:
# Find the inorder predecessor of current
pre = current.left
while(pre.right is not None and pre.right != current):
pre = pre.right
# Make current as right child of its inorder predecessor
if(pre.right is None):
pre.right = current
current = current.left
# Revert the changes made in if part to restore the
# original tree i.e., fix the right child of predecssor
else:
pre.right = None
print(current.val, end=" ")
current = current.right
print()
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
morris_inorder_traversal(root)
Output:
Check if bianry tree is height balanced by considering a height-balancing scheme where following conditions should be checked to determine if a binary tree is balanced.
def height(root):
if root is None:
return 0
return max(height(root.left), height(root.right)) + 1
# function to check if tree is height-balanced or not
def isBalanced(root):
if root is None:
return True
# left and right subtree height
lh = height(root.left)
rh = height(root.right)
# allowed values for (lh - rh) are 1, -1, 0
if (abs(lh-rh) <= 1) and isBalanced(root.left) and isBalanced( root.right):
return True
# if we reach here means tree is not height-balanced tree
return False
class Node:
def __init__(self, data):
self.data = data
self.left = self.right = None
class Height:
def __init__(self):
self.height = 0
def isBalanced(root, height):
# lh and rh to store height of left and right subtree
lh = Height()
rh = Height()
if root is None:
return True
# l and r are used to check if left and right subtree are balanced
l = isBalanced(root.left, lh)
r = isBalanced(root.right, rh)
# Update height
height.height = max(lh.height, rh.height) + 1
if abs(lh.height-rh.height) <= 1 and l and r:
return True
# if we reach here then the tree is not balanced
return False
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.left.left.left = Node(7)
if isBalanced(root, Height()):
print('Tree is balanced')
else:
print('Tree is not balanced')
class Node:
def __init__(self, key):
self.val = key
self.left = None
self.right = None
self.rightThread = False
Whether we will be able to construct a binary tree with given 2 traversals depends on what traversals are given.
If one of the traversal methods is Inorder then the tree can be constructed, otherwise not.
Therefore, following combination can uniquely identify a tree.
In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences.
By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree.
class Node:
def __init__(self, key):
self.val = key
self.left = None
self.right = None
# Recursive function to construct binary of size len from
# Inorder traversal inorder[] and Preorder traversal preorder[].
# Initial values of inorder_start and inorder_end should be 0 and len -1.
# The function doesn't do any error checking for cases where inorder and preorder do not form a tree.
def build_tree(inorder, preorder, inorder_start, inorder_end):
if (inorder_start > inorder_end):
return None
# Pick current node from Preorder traversal using preorder_index and increment preorder_index
# Create a new tree node with this picked element
tree_node = Node(preorder[build_tree.preorder_index])
build_tree.preorder_index += 1
# If this node has no children then return
if inorder_start == inorder_end :
return tree_node
# Else find the index of this node in Inorder traversal
inorder_index = search(inorder, inorder_start, inorder_end, tree_node.val)
# Using index in Inorder Traversal, construct left and right subtrees
tree_node.left = build_tree(inorder, preorder, inorder_start, inorder_index-1)
tree_node.right = build_tree(inorder, preorder, inorder_index+1, inorder_end)
return tree_node
# Function to find index of vaue in arr[start...end]
# The function assumes that value is rpesent in inorder[]
def search(arr, start, end, value):
for i in range(start, end+1):
if arr[i] == value:
return i
def inorder_traversal(node):
if node is None:
return
inorder_traversal(node.left)
print (node.val, end=" ")
inorder_traversal(node.right)
# Driver program to test above function
inorder = ['D', 'B' ,'E', 'A', 'F', 'C']
preorder = ['A', 'B', 'D', 'E', 'C', 'F']
# Static variable preorder_index
build_tree.preorder_index = 0
root = build_tree(inorder, preorder, 0, len(inorder)-1)
# Let us test the build tree by priting Inorder traversal
print ("Inorder traversal of the constructed tree is:")
inorder_traversal(root)
print()
Output:
Worst case occurs when tree is left skewed.
Example Preorder and Inorder traversals for worst case are {A, B, C, D} and {D, C, B, A}.
Left-Root-Right
and Preorder traversal is Root-Left-Right
. Stack (to store the path visited while traversing Preorder array) and Set (to maintain the node in which the next right subtree is expected).
Do below until reach the leftmost node.
Keep creating the nodes from Preorder traversal
If the stack’s topmost element is not in the set, link the created node to the left child of stack’s topmost element (if any), without popping the element.
Else link the created node to the right child of stack’s topmost element and then remove the stack’s topmost element from the set and the stack.
Push the node to stack.
Keep popping the nodes from the stack until either the stack is empty, or the topmost element of stack compares to the current element of Inorder traversal. Once the loop is over, push the last node back into the stack and into the set.
Go to Step 1.