Trees_strategy

Question 1

/When we say two trees are identical?

what Data structure we use for iterative solution?

Answer 1

Two trees are identical id they have same contents and same structures

in iterative implementation we use stack = deque()

Question 2

What is the time and space complexity in the algorithm for checking whether two trees are identical?

Answer 2

for both iterative and recursive, time complexity is O(n)

Space complexity in iterative is O(n) since we use stack

for recursive space complexity is proportional to the trees hight

Question 3

Check if two binary trees are identical or not – Iterative

Answer 3

Algorithm:

1) check if x and y are both None –> return True
2) check if only x is None –> return False
3) check if only y is None –> return False
5) define stack = deque()
6) append a pair of (x,y)
7) while stack:
8) pop the top pair from stack
9) check if their key values are not equal, return False
10) check if they have left child: append the left child to the stack
11) elif x.left or y.left: retur False
12) do 10, 11 for right

code

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Iterative function to check if two given binary trees are identical or not
def isIdentical(x, y):

    # if both trees are empty, return true
    if x is None and y is None:
        return True

    # if the first tree is empty (and the second tree is non-empty), return false
    if x is None:
        return False

    # if the second tree is empty (and the first tree is non-empty), return false
    if y is None:
        return False

    # create a stack to hold pairs
    stack = deque()
    stack.append((x, y))

    # loop till stack is empty
    while stack:
        # pop the top pair from the stack and process it
        x, y = stack.pop()

        # if the value of their root node doesn't match, return false
        if x.key != y.key:
            return False

    # if the left subtree of both `x` and `y` exists, push their addresses
    # to stack; otherwise, return false if only one left child exists
    if x.left and y.left:
        stack.append((x.left, y.left))
    elif x.left or y.left:
        return False

    # if the right subtree of both `x` and `y` exists, push their addresses
    # to stack; otherwise, return false if only one right child exists
    if x.right and y.right:
        stack.append((x.right, y.right))
    elif x.right or y.right:
        return False

    # we reach here if both binary trees are identical
    return True

if __name__ == ‘__main__’:

    # construct the first tree
    x = Node(15)
    x.left = Node(10)
    x.right = Node(20)
    x.left.left = Node(8)
    x.left.right = Node(12)
    x.right.left = Node(16)
    x.right.right = Node(25)

    # construct the second tree
    y = Node(15)
    y.left = Node(10)
    y.right = Node(20)
    y.left.left = Node(8)
    y.left.right = Node(12)
    y.right.left = Node(16)
    y.right.right = Node(25)

    if isIdentical(x, y):
        print('The given binary trees are identical')
    else:
        print('The given binary trees are not identical')from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Iterative function to check if two given binary trees are identical or not
def isIdentical(x, y):

    # if both trees are empty, return true
    if x is None and y is None:
        return True

    # if the first tree is empty (and the second tree is non-empty), return false
    if x is None:
        return False

    # if the second tree is empty (and the first tree is non-empty), return false
    if y is None:
        return False

    # create a stack to hold pairs
    stack = deque()
    stack.append((x, y))

    # loop till stack is empty
    while stack:
        # pop the top pair from the stack and process it
        x, y = stack.pop()

        # if the value of their root node doesn't match, return false
        if x.key != y.key:
            return False

    # if the left subtree of both `x` and `y` exists, push their addresses
    # to stack; otherwise, return false if only one left child exists
    if x.left and y.left:
        stack.append((x.left, y.left))
    elif x.left or y.left:
        return False

    # if the right subtree of both `x` and `y` exists, push their addresses
    # to stack; otherwise, return false if only one right child exists
    if x.right and y.right:
        stack.append((x.right, y.right))
    elif x.right or y.right:
        return False

    # we reach here if both binary trees are identical
    return True

if __name__ == ‘__main__’:

    # construct the first tree
    x = Node(15)
    x.left = Node(10)
    x.right = Node(20)
    x.left.left = Node(8)
    x.left.right = Node(12)
    x.right.left = Node(16)
    x.right.right = Node(25)

    # construct the second tree
    y = Node(15)
    y.left = Node(10)
    y.right = Node(20)
    y.left.left = Node(8)
    y.left.right = Node(12)
    y.right.left = Node(16)
    y.right.right = Node(25)

    if isIdentical(x, y):
        print('The given binary trees are identical')
    else:
        print('The given binary trees are not identical')

Question 4

Check if two binary trees are identical or not Recursive

Write an efficient algorithm to check if two binary trees are identical or not. Two binary trees are identical if they have identical structure and their contents are also the same.

Answer 4

Algorithm :

1) if both trees are empty, return true
2) if both tree are not empty, and their keys are equal , recur function for x.left , y.left, x.right, y.righ

code

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Recursive function to check if two given binary trees are identical or not
def isIdentical(x, y):

    # if both trees are empty, return true
    if x is None and y is None:
        return True

    # if both trees are non-empty and the value of their root node matches,
    # recur for their left and right subtree
    return (x is not None and y is not None) and (x.key == y.key) and \
        isIdentical(x.left, y.left) and isIdentical(x.right, y.right)

if __name__ == ‘__main__’:

    # construct the first tree
    x = Node(15)
    x.left = Node(10)
    x.right = Node(20)
    x.left.left = Node(8)
    x.left.right = Node(12)
    x.right.left = Node(16)
    x.right.right = Node(25)

    # construct the second tree
    y = Node(15)
    y.left = Node(10)
    y.right = Node(20)
    y.left.left = Node(8)
    y.left.right = Node(12)
    y.right.left = Node(16)
    y.right.right = Node(25)

    if isIdentical(x, y):
        print('The given binary trees are identical')
    else:
        print('The given binary trees are not identical')

Question 5

1) 2 types of Tree traversal

2) 2 types of traversal algorithm implementations

Answer 5

1) depth-first search ( going down the tree)
pre order, post order, inorder
breath first search tree –> level order traversal

2) algorithms could be implemented is recursion manner where data stored in the call stack
or in iterative order where the data stored in the stacks

Question 6

implement post order tree traversal in recursive

Answer 6

For traversing a (non-empty) binary tree in a postorder fashion, we must do these three things for every node n starting from the tree’s root:

(L) Recursively traverse its left subtree. When this step is finished, we are back at n again.
(R) Recursively traverse its right subtree. When this step is finished, we are back at n again.
(N) Process n itself.

As we can see, before processing any node, the left subtree is processed first, followed by the right subtree, and the node is processed at last. These operations can be defined recursively for each node. The recursive implementation is referred to as a Depth–first search (DFS), as the search tree is deepened as much as possible on each child before going to the next sibling.
________ code________

# Data structure to store a binary tree node
class Node:
    def \_\_init\_\_(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Recursive function to perform postorder traversal on the tree
def postorder(root):

    # return if the current node is empty
    if root is None:
        return

    # Traverse the left subtree
    postorder(root.left)

    # Traverse the right subtree
    postorder(root.right)

    # Display the data part of the root (or current node)
    print(root.data, end=' ')

if __name__ == ‘__main__’:

    ''' Construct the following tree
               1
             /   \
            /     \
           2       3
          /      /   \
         /      /     \
        4      5       6
              / \
             /   \
            7     8
    '''

root = Node(1)

root. left = Node(2)
root. right = Node(3)
root. left.left = Node(4)
root. right.left = Node(5)
root. right.right = Node(6)
root. right.left.left = Node(7)
root. right.left.right = Node(8)

postorder(root)

Question 7

Post order tree traversal, iterative

Answer 7

iterativePostorder(node)

s —> empty stack
t —> output stack
while (not s.isEmpty())
  node —> s.pop()
  t.push(node)

if (node.left <> null)
s.push(node.left)

if (node.right <> null)
s.push(node.right)

while (not t.isEmpty())
node —> t.pop()
visit(node)

https://www.techiedelight.com/postorder-tree-traversal-iterative-recursive/

________ code

from collections import deque

# Data structure to store a binary tree node
class Node:
    def \_\_init\_\_(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Iterative function to perform postorder traversal on the tree
def postorderIterative(root):

    # return if the tree is empty
    if root is None:
        return

    # create an empty stack and push the root node
    stack = deque()
    stack.append(root)

    # create another stack to store postorder traversal
    out = deque()

    # loop till stack is empty
    while stack:

        # pop a node from the stack and push the data into the output stack
        curr = stack.pop()
        out.append(curr.data)

    # push the left and right child of the popped node into the stack
    if curr.left:
        stack.append(curr.left)

    if curr.right:
        stack.append(curr.right)

    # print postorder traversal
    while out:
        print(out.pop(), end=' ')

if __name__ == ‘__main__’:

    ''' Construct the following tree
               1
             /   \
            /     \
           2       3
          /      /   \
         /      /     \
        4      5       6
              / \
             /   \
            7     8
    '''

root = Node(1)

root. left = Node(2)
root. right = Node(3)
root. left.left = Node(4)
root. right.left = Node(5)
root. right.right = Node(6)
root. right.left.left = Node(7)
root. right.left.right = Node(8)

postorderIterative(root)

Question 8

In-order tree traversal recurssion

Answer 8

# Data structure to store a binary tree node
class Node:
    def \_\_init\_\_(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Recursive function to perform inorder traversal on the tree
def inorder(root):

    # return if the current node is empty
    if root is None:
        return

    # Traverse the left subtree
    inorder(root.left)

    # Display the data part of the root (or current node)
    print(root.data, end=' ')

    # Traverse the right subtree
    inorder(root.right)

if __name__ == ‘__main__’:

    ''' Construct the following tree
               1
             /   \
            /     \
           2       3
          /      /   \
         /      /     \
        4      5       6
              / \
             /   \
            7     8
    '''

root = Node(1)

root. left = Node(2)
root. right = Node(3)
root. left.left = Node(4)
root. right.left = Node(5)
root. right.right = Node(6)
root. right.left.left = Node(7)
root. right.left.right = Node(8)

inorder(root)

Question 9

Inorder traversal itteratively

Answer 9

iterativeInorder(node)

  s —> empty stack
  while (not s.isEmpty() or node != null)
    if (node != null)
      s.push(node)
      node —> node.left
    else
      node —> s.pop()
      visit(node)
      node —> node.right

code############

from collections import deque

# Data structure to store a binary tree node
class Node:
    def \_\_init\_\_(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Iterative function to perform inorder traversal on the tree
def inorderIterative(root):

    # create an empty stack
    stack = deque()

    # start from the root node (set current node to the root node)
    curr = root

    # if the current node is None and the stack is also empty, we are done
    while stack or curr:

    # if the current node exists, push it into the stack (defer it)
    # and move to its left child
    if curr:
        stack.append(curr)
        curr = curr.left
    else:
        # otherwise, if the current node is None, pop an element from the stack,
        # print it, and finally set the current node to its right child
        curr = stack.pop()
        print(curr.data, end=' ')

        curr = curr.right

if __name__ == ‘__main__’:

    ''' Construct the following tree
               1
             /   \
            /     \
           2       3
          /      /   \
         /      /     \
        4      5       6
              / \
             /   \
            7     8
    '''

root = Node(1)

root. left = Node(2)
root. right = Node(3)
root. left.left = Node(4)
root. right.left = Node(5)
root. right.right = Node(6)
root. right.left.left = Node(7)
root. right.left.right = Node(8)

inorderIterative(root)

Question 10

Pre-order traversal of Tree recurssion

Answer 10

As we can see, only after processing any node, the left subtree is processed, followed by the right subtree. These operations can be defined recursively for each node. The recursive implementation is referred to as a Depth–first search (DFS), as the search tree is deepened as much as possible on each child before going to the next sibling.

# Data structure to store a binary tree node
class Node:
    def \_\_init\_\_(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Recursive function to perform preorder traversal on the tree
def preorder(root):

    # return if the current node is empty
    if root is None:
        return

    # Display the data part of the root (or current node)
    print(root.data, end=' ')

    # Traverse the left subtree
    preorder(root.left)

    # Traverse the right subtree
    preorder(root.right)

if __name__ == ‘__main__’:

    ''' Construct the following tree
               1
             /   \
            /     \
           2       3
          /      /   \
         /      /     \
        4      5       6
              / \
             /   \
            7     8
    '''

root = Node(1)

root. left = Node(2)
root. right = Node(3)
root. left.left = Node(4)
root. right.left = Node(5)
root. right.right = Node(6)
root. right.left.left = Node(7)
root. right.left.right = Node(8)

preorder(root)

Question 11

Pre-order iteratively

Answer 11

iterativePreorder(node)

if (node = null)
  return
s —> empty stack
s.push(node)
while (not s.isEmpty())
  node —> s.pop()
  visit(node)
  if (node.right != null)
    s.push(node.right)
  if (node.left != null)
    s.push(node.left)

################# code
from collections import deque

# Data structure to store a binary tree node
class Node:
    def \_\_init\_\_(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Iterative function to perform preorder traversal on the tree
def preorderIterative(root):

    # return if the tree is empty
    if root is None:
        return

    # create an empty stack and push the root node
    stack = deque()
    stack.append(root)

    # loop till stack is empty
    while stack:

        # pop a node from the stack and print it
        curr = stack.pop()

    print(curr.data, end=' ')

    # push the right child of the popped node into the stack
    if curr.right:
        stack.append(curr.right)

    # push the left child of the popped node into the stack
    if curr.left:
        stack.append(curr.left)

    # the right child must be pushed first so that the left child
    # is processed first (LIFO order)

if __name__ == ‘__main__’:

    ''' Construct the following tree
               1
             /   \
            /     \
           2       3
          /      /   \
         /      /     \
        4      5       6
              / \
             /   \
            7     8
    '''

root = Node(1)

root. left = Node(2)
root. right = Node(3)
root. left.left = Node(4)
root. right.left = Node(5)
root. right.right = Node(6)
root. right.left.left = Node(7)
root. right.left.right = Node(8)

preorderIterative(root)

Question 12

Calculate the height of a binary tree recursive

Answer 12

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Recursive function to calculate the height of a given binary tree
def height(root):

    # base case: empty tree has a height of 0
    if root is None:
        return 0

    # recur for the left and right subtree and consider maximum depth
    return 1 + max(height(root.left), height(root.right))

if __name__ == ‘__main__’:

root = Node(15)

root. left = Node(10)
root. right = Node(20)
root. left.left = Node(8)
root. left.right = Node(12)
root. right.left = Node(16)
root. right.right = Node(25)

print('The height of the binary tree is', height(root))

Question 13

Calculate the height of a binary tree itterative

Answer 13

The idea is to traverse the tree in a postorder fashion and calculate the height of the left and right subtree. The height of a subtree rooted at any node will be one more than the maximum height of its left and right subtree. Recursively apply this property to all tree nodes in a bottom-up manner (postorder fashion) and return the subtree’s maximum height rooted at that node.
###### code#################

def deleteTree(root):
    if root:
        # delete left subtree
        deleteTree(root.leftChild)
        # delete right subtree
        deleteTree(root.rightChild)
        # traverse root
        print("Deleting Node:", root.data)
        del root

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, data, left=None, right=None):
        self.key = data
        self.left = left
        self.right = right

# Iterative function to calculate the height of a given binary tree
# by doing level order traversal on the tree
def height(root):

    # empty tree has a height of 0
    if root is None:
        return 0

    # create an empty queue and enqueue the root node
    queue = deque()
    queue.append(root)

height = 0

    # loop till queue is empty
    while queue:

        # calculate the total number of nodes at the current level
        size = len(queue)

        # process each node of the current level and enqueue their
        # non-empty left and right child
        while size > 0:
            front = queue.popleft()

        if front.left:
            queue.append(front.left)

        if front.right:
            queue.append(front.right)

        size = size - 1

        # increment height by 1 for each level
        height = height + 1

return height

Question 14

Claculate the height of a binary tree, itteratively

Answer 14

We need to traverse by level order of a tree and calculate the tree level.

then need to modify Breadth First Search:

algorith:
- if root is None -> return0
- q --> empty queu()
- q.enqueue(root)
- hight = 0 
- while not q.isEmpty()
      size -> len(stack)
      while size:
             front -> stack.popleft()
             if front.left --> stack.enqueueu(front.left)
             f front.right --> stack.enqueueu(front.right)

  hight+1

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, data, left=None, right=None):
        self.key = data
        self.left = left
        self.right = right

# Iterative function to calculate the height of a given binary tree
# by doing level order traversal on the tree
def height(root):

    # empty tree has a height of 0
    if root is None:
        return 0

    # create an empty queue and enqueue the root node
    queue = deque()
    queue.append(root)

height = 0

    # loop till queue is empty
    while queue:

        # calculate the total number of nodes at the current level
        size = len(queue)

        # process each node of the current level and enqueue their
        # non-empty left and right child
        while size > 0:
            front = queue.popleft()

        if front.left:
            queue.append(front.left)

        if front.right:
            queue.append(front.right)

        size = size - 1

        # increment height by 1 for each level
        height = height + 1

return height

Question 15

Breadth First serch - level order traversal in recurssion

Answer 15

A simple solution is to print all nodes of level 1 first, followed by level 2, until level h, where h is the tree’s height. We can print all nodes present in a level by modifying the preorder traversal on the tree.

The time complexity of the above solution is O(n2), where n is the total number of nodes in the binary tree. The auxiliary space required by the program is O(h) for the call stack, where h is the height of the tree

############# code#########
# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Function to print all nodes of a given level from left to right
def printLevel(root, level):

    # base case
    if root is None:
        return False

if level == 1:
    print(root.key, end=' ')

        # return true if at least one node is present at a given level
        return True

left = printLevel(root.left, level - 1)
right = printLevel(root.right, level - 1)

return left or right

# Function to print level order traversal of a given binary tree
def levelOrderTraversal(root):

    # start from level 1 — till the height of the tree
    level = 1

    # run till printLevel() returns false
    while printLevel(root, level):
        level = level + 1

if __name__ == ‘__main__’:

root = Node(15)

root. left = Node(10)
root. right = Node(20)
root. left.left = Node(8)
root. left.right = Node(12)
root. right.left = Node(16)
root. right.right = Node(25)

levelOrderTraversal(root)

Question 16

Breadth -First- Serach, iteratively

Answer 16

We can reduce the time complexity to O(n) by using extra space. Following is a pseudocode for a simple queue-based level order traversal, which requires space proportional to the maximum number of nodes at a given depth. It can be as much as half the total number of nodes.

levelorder(root)
q —> empty queue
q.enqueue(root)
while (not q.isEmpty())
  node —> q.dequeue()
  visit(node)
  if (node.left <> null)
    q.enqueue(node.left)
  if (node.right <> null)
    q.enqueue(node.right)
#######################code############

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Function to print level order traversal of a given binary tree
def levelOrderTraversal(root):

    # base case
    if not root:
        return

    # create an empty queue and enqueue the root node
    queue = deque()
    queue.append(root)

    # loop till queue is empty
    while queue:

        # process each node in the queue and enqueue their
        # non-empty left and right child
        curr = queue.popleft()

    print(curr.key, end=' ')

    if curr.left:
        queue.append(curr.left)

    if curr.right:
        queue.append(curr.right)

if __name__ == ‘__main__’:

root = Node(15)

root. left = Node(10)
root. right = Node(20)
root. left.left = Node(8)
root. left.right = Node(12)
root. right.left = Node(16)
root. right.right = Node(25)

levelOrderTraversal(root)

Question 17

Level order traversal (BDS) of a tree using multimap :)

Very Very Important

Answer 17

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Traverse the tree in a preorder fashion and store nodes in a dictionary
# corresponding to their level
def preorder(root, level, d):

    # base case: empty tree
    if root is None:
        return

    # insert the current node and its level into the dictionary
    d.setdefault(level, []).append(root.key)

# recur for the left and right subtree by increasing the level by 1
preorder(root.left, level + 1, d)
preorder(root.right, level + 1, d)

# Recursive function to print level order traversal of a given binary tree
def levelOrderTraversal(root):

    # create an empty dictionary to store nodes between given levels
    d = {}

    # traverse the tree and insert its nodes into the dictionary
    # corresponding to their level
    preorder(root, 1, d)

    # iterate through the dictionary and print all nodes between given levels
    for i in range(1, len(d) + 1):
        print(f'Level {i}:', d[i])

if __name__ == ‘__main__’:

root = Node(15)

root. left = Node(10)
root. right = Node(20)
root. left.left = Node(8)
root. left.right = Node(12)
root. right.left = Node(16)
root. right.right = Node(25)
root. right.right.right = Node(30)

levelOrderTraversal(root)

Question 18

Spiral order traversal of a binary tree – iteratively

Given a binary tree, print its nodes level by level in spiral order, i.e., all nodes present at level 1 should be printed first from left to right, followed by nodes of level 2 from right to left, followed by nodes of level 3 from left to right and so on… In other words, odd levels should be printed from left to right, and even levels should be printed from right to left or vice versa.

For example, the spiral level order traversal for the following tree is

(1, 3, 2, 4, 5, 6, 7) or (1, 2, 3, 7, 6, 5, 4)

Answer 18

The time complexity of the above solution is O(n2), where n is the total number of nodes in the binary tree.

We can reduce the time complexity to O(n) by using extra space. Following is a pseudocode for a simple queue-based spiral order traversal:

levelorder(root)
q —> empty double ended queue
q.push(root)
while (not q.isEmpty())
  while (level is even)
    node —> q.popFront()
    visit(node)
    if (node.left <> null)
      q.pushBack(node.left)
    if (node.right <> null)
      q.pushBack(node.right)

  while (level is odd)
    node —> q.popBack()
    visit(node)
    if (node.right <> null)
      q.pushFront(node.right)
    if (node.left <> null)
      q.pushFront(node.left)

https://www.techiedelight.com/spiral-order-traversal-binary-tree/

code##############

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Function to print spiral order traversal of a given binary tree
def spiralOrderTraversal(root):

if root is None:
    return

    # create an empty double-ended queue and enqueue the root node
    q = deque()         # or use deque
    q.appendleft(root)

    # `flag` is used to differentiate between odd or even level
    flag = True

    # loop till deque is empty
    while q:

        # calculate the total number of nodes at the current level
        nodeCount = len(q)

        # print left to right
        if flag:
            # process each node of the current level and enqueue their
            # non-empty left and right child to deque
            while nodeCount > 0:
                # pop from the front if `flag` is true
                curr = q.popleft()
                print(curr.key, end=' ')

                # it is important to push the left child into the back,
                # followed by the right child

            if curr.left:
                q.append(curr.left)

            if curr.right:
                q.append(curr.right)

            nodeCount = nodeCount - 1

        # print right to left
        else:
            # process each node of the current level and enqueue their
            # non-empty right and left child
            while nodeCount > 0:
                # it is important to pop from the back
                curr = q.pop()
                print(curr.key, end=' ')    # print front node

                # it is important to push the right child at the front,
                # followed by the left child

            if curr.right:
                q.appendleft(curr.right)

            if curr.left:
                q.appendleft(curr.left)

            nodeCount = nodeCount - 1

        # flip the flag for the next level
        flag = not flag
        print()

if __name__ == ‘__main__’:

root = Node(15)

root. left = Node(10)
root. right = Node(20)
root. left.left = Node(8)
root. left.right = Node(12)
root. right.left = Node(16)
root. right.right = Node(25)

spiralOrderTraversal(root)

Question 19

Spiral order traversal of a binary tree – using multimap

Given a binary tree, print its nodes level by level in spiral order, i.e., all nodes present at level 1 should be printed first from left to right, followed by nodes of level 2 from right to left, followed by nodes of level 3 from left to right and so on… In other words, odd levels should be printed from left to right, and even levels should be printed from right to left or vice versa.

For example, the spiral level order traversal for the following tree is

Answer 19

We can also solve this problem by using hashing. The following code traverses the tree in a preorder fashion and uses a map to store every node and its level using the level number as a key.

The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the size of the binary tree.

code ###########

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Traverse the tree in a preorder fashion and store nodes in a dictionary
# corresponding to their level
def preorder(root, level, d):

    # base case: empty tree
    if root is None:
        return

# insert the current node and its level into the dictionary
# if the level is odd, insert at the back; otherwise, search at front
if level % 2 == 1:
    d.setdefault(level, deque()).append(root.key)
else:
    d.setdefault(level, deque()).appendleft(root.key)

# recur for the left and right subtree by increasing the level by 1
preorder(root.left, level + 1, d)
preorder(root.right, level + 1, d)

# Recursive function to print spiral order traversal of a given binary tree
def levelOrderTraversal(root):

    # create an empty dictionary to store nodes between given levels
    d = {}

    # traverse the tree and insert its nodes into the dictionary
    # corresponding to their level
    preorder(root, 1, d)

    # iterate through the dictionary and print all nodes present at every level
    for i in range(1, len(d) + 1):
        print(f'Level {i}:', list(d[i]))

if __name__ == ‘__main__’:

root = Node(15)

root. left = Node(10)
root. right = Node(20)
root. left.left = Node(8)
root. left.right = Node(12)
root. right.left = Node(16)
root. right.right = Node(25)
root. left.left.left = Node(20)
root. right.right.right = Node(30)

levelOrderTraversal(root)

Question 20

Reverse level order traversal of a binary tree — iterattively

Given a binary tree, print its nodes level by level in reverse order, i.e., print all nodes present at the last level first, followed by nodes of the second last level, and so on… Print nodes at any level from left to right.

Answer 20

levelorder(root)

q —> empty queue
s —> empty stack
q.enqueue(root)
while (not q.isEmpty())
  node —> q.dequeue()
  s.push(node)
  if (node.right <> null)
    q.enqueue(node.right)
  if (node.left <> null)
    q.enqueue(node.left)

while (not s.isEmpty())
node —> s.pop()
print(node)

time and space : O(n)
https://www.techiedelight.com/reverse-level-order-traversal-binary-tree/
########## code##########

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Function to print reverse level order traversal of a given binary tree
def reverseLevelOrderTraversal(root):

if root is None:
    return

    # create an empty queue and enqueue the root node
    queue = deque()
    queue.append(root)

    # create a stack to reverse level order nodes
    stack = deque()

    # loop till queue is empty
    while queue:

        # process each node in the queue and enqueue their children
        curr = queue.popleft()

        # push the current node into the stack
        stack.append(curr.key)

    # it is important to process the right node before the left node
    if curr.right:
        queue.append(curr.right)

    if curr.left:
        queue.append(curr.left)

    # pop all nodes from the stack and print them
    while stack:
        print(stack.pop(), end=' ')

if __name__ == ‘__main__’:

root = Node(15)

root. left = Node(10)
root. right = Node(20)
root. left.left = Node(8)
root. left.right = Node(12)
root. right.left = Node(16)
root. right.right = Node(25)

reverseLevelOrderTraversal(root)

Question 21

Reverse level order traversal of a binary tree — using multimap(hashing)

Given a binary tree, print its nodes level by level in reverse order, i.e., print all nodes present at the last level first, followed by nodes of the second last level, and so on… Print nodes at any level from left to right.

Answer 21

using preorder traversal and modifying it

code

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Traverse the tree in a preorder fashion and store nodes in a 
dictionary
# corresponding to their level
def preorder(root, level, d):

    # base case: empty tree
    if root is None:
        return

    # insert the current node and its level into the dictionary
    d.setdefault(level, []).append(root.key)

# recur for the left and right subtree by increasing the level by 1
preorder(root.left, level + 1, d)
preorder(root.right, level + 1, d)

# Recursive function to perform reverse level order traversal on a binary tree
def levelOrderTraversal(root):

    # create an empty dictionary to store nodes between given levels
    d = {}

    # traverse the tree and insert its nodes into the dictionary
    # corresponding to their level
    preorder(root, 1, d)

    # iterate through the dictionary in reverse order and
    # print all nodes present at every level
    for i in range(len(d), 0, -1):
        print(f'Level {i}:', d.get(i))

if __name__ == ‘__main__’:

root = Node(15)

root. left = Node(10)
root. right = Node(20)
root. left.left = Node(8)
root. left.right = Node(12)
root. right.left = Node(16)
root. right.right = Node(25)
root. right.right.right = Node(30)

levelOrderTraversal(root)

Question 22

Given a perfect binary tree, print the values of alternating left and right nodes for each level in a top-down

Answer 22

The idea is to modify level order traversal by maintaining two queues. We process two nodes each from one queue and enqueue the left and right child of the first popped node into the first queue and the right and left child of the second popped node into the second queue.

https://www.techiedelight.com/print-nodes-binary-tree-specific-order/

code

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Function to print all nodes of a given binary tree in a specific
# order from top to bottom
def printNodes(root):

    # return if the tree is empty
    if root is None:
        return

    # print the root node
    print(root.key, end=' ')

    # create two empty queues and enqueue root's left and
    # right child, respectively
    q1 = deque()
    q2 = deque()

if root.left and root.right:

    q1. append(root.left)
    q2. append(root.right)

    # loop till queue is empty
    while q1:

        # calculate the total number of nodes at the current level
        n = len(q1)

        # process every node of the current level
        for _ in range(n):

            # dequeue front node from the first queue and print it
            x = q1.popleft()

        print(x.key, end=' ')

        # enqueue left and right child of `x` to the first queue
        if x.left:
            q1.append(x.left)

        if x.right:
            q1.append(x.right)

            # dequeue front node from the second queue and print it
            y = q2.popleft()

        print(y.key, end=' ')

        # enqueue right and left child of `y` to the second queue
        if y.right:
            q2.append(y.right)

        if y.left:
            q2.append(y.left)

if __name__ == ‘__main__’:

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. right.right = Node(7)
root. left.left.left = Node(8)
root. left.left.right = Node(9)
root. left.right.left = Node(10)
root. left.right.right = Node(11)
root. right.left.left = Node(12)
root. right.left.right = Node(13)
root. right.right.left = Node(14)
root. right.right.right = Node(15)

printNodes(root)

Question 23

Given a perfect binary tree, print the values of alternating left and right nodes for each level in a bottom up

Answer 23

The idea is to store nodes of every level in the desired order in a map and finally print nodes from the map for each level, starting from the last level to the first level.

The time complexity of the solution is O(n.log(n)) and requires O(n) extra space, where n is the size of the binary tree.

code########

def print_left_right_bottom_up(root):
    if root is None:
        return

d ={}
level = 1
d.setdefault(level, []).append(root.key)

q1 = deque()
q2 = deque()

if root.left and root.right:

    q1. append(root.left)
    q2. append(root.right)

while q1:
    level = level + 1
    n = len(q1)

        while n > 0:
            x = q1.popleft()
            d.setdefault(level, []).append(x.key)
            if x.left:
                q1.append(x.left)
            if x.right:
                q1.append(x.right)

        y = q2.popleft()
        d.get(level).append(y.key)

            if y.left:
                q2.append(y.left)
            if y.right:
                q2.append(y.right)
            n -= 1
    for i in reversed(d.keys()):
        print(d.get(i))

Question 24

Print left view of a binary tree iteratively

Given a binary tree, write an efficient algorithm to print its left view.

Answer 24

In the iterative version, perform a level order traversal on the tree. We can modify level order traversal to maintain nodes at the current level. Then if the current node is the first node of the current level, print it.

techiedelight.com/print-left-view-of-binary-tree/
########## code

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Iterative function to print the left view of a given binary tree
def leftView(root):

    # return if the tree is empty
    if root is None:
        return

    # create an empty queue and enqueue the root node
    queue = deque()
    queue.append(root)

    # loop till queue is empty
    while queue:

        # calculate the total number of nodes at the current level
        size = len(queue)
        i = 0

        # process every node of the current level and enqueue their
        # non-empty left and right child
        while i < size:
            # pointer to store the current node
            curr = queue.popleft()
            i = i + 1

            # if this is the first node of the current level, print it
            if i == 1:
                print(curr.key, end=' ')

        if curr.left:
            queue.append(curr.left)

        if curr.right:
            queue.append(curr.right)

if __name__ == ‘__main__’:

root = Node(1)

root. left = Node(2)
root. right = Node(3)
root. left.right = Node(4)
root. right.left = Node(5)
root. right.right = Node(6)
root. right.left.left = Node(7)
root. right.left.right = Node(8)

leftView(root)

Question 25

What is the Horizantal distance?

Answer 25

Horizontal Distance (HD): is the distance of a node from the root node. The HD of the root node is zero. Any node that falls in the vertical line after the root node line will be positive, and any node that falls in the vertical line to the left of the root node will be negative.

Question 26

Print bottom view of a binary tree

Given a binary tree, print the bottom view of it. Assume the left and right child of a node makes a 45–degree angle with the parent.

Answer 26

For solving this question we need to have distance of each node till root.
like other level traversal tree which we use hashmap, here we also fill a hashmap while we traverse a tree in modified preorder.
The difference here is that for preorder function, we have (root, dist, level, d)
1) when we visit a node, we check wether the dist is for the first-time in d OR level >= d[dist], then we update d with dist as ke and a pair of value and level:
d[dist] = (node.key, level)

2) for left child of the node we decrease distance and increase level
3) for right chile of the node we increase both distance and level

at the end in second function where we print the hashmap, we sort hashmap keys and the print the values. 
sorted(d.keys())
############# code

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Recursive function to perform preorder traversal on the tree and fill the map.
# Here, the node has `dist` horizontal distance from the tree's root,
# and the `level` represents the node's level.
def printBottom(root, dist, level, d):

    # base case: empty tree
    if root is None:
        return

# if the current level is more than or equal to the maximum level seen so far
# for the same horizontal distance or horizontal distance is seen for
# the first time, update the dictionary
if dist not in d or level >= d[dist][1]:
    # update value and level for the current distance
    d[dist] = (root.key, level)

    # recur for the left subtree by decreasing horizontal distance and
    # increasing level by 1
    printBottom(root.left, dist - 1, level + 1, d)

    # recur for the right subtree by increasing both level and
    # horizontal distance by 1
    printBottom(root.right, dist + 1, level + 1, d)

# Function to print the bottom view of a given binary tree
def printBottomView(root):

    # create a dictionary where
    # key —> relative horizontal distance of the node from the root node, and
    # value —> pair containing the node's value and its level
    d = {}

    # perform preorder traversal on the tree and fill the dictionary
    printBottom(root, 0, 0, d)

    # traverse the dictionary in sorted order of their keys and
    # print the bottom view
    for key in sorted(d.keys()):
        print(d.get(key)[0], end=' ')

if __name__ == ‘__main__’:

root = Node(1)

root. left = Node(2)
root. right = Node(3)
root. left.right = Node(4)
root. right.left = Node(5)
root. right.right = Node(6)
root. right.left.left = Node(7)
root. right.left.right = Node(8)

printBottomView(root)

Question 27

Print left view of a binary tree - hashmap

Given a binary tree, write an efficient algorithm to print its left view.

Answer 27

Like other print levels, we use modified preorder solution.
instead of printing root or adding it on the dictionart, we make a constrane that if level is not in d, add the value to the d[level]. in this case the first node in each level will be added to the dict. 
O(n)
##################code:#######

class Node:
    def \_\_init\_\_(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Recursive function to traverse the nodes in a preorder fashion
def leftView(root, level, d):

    # base case
    if root is None:
        return

    # if the level is visited for the first time, insert the current node
    # and level information into the dictionary
    if level not in d:
        d[level] = root.key

leftView(root.left, level + 1, d)
leftView(root.right, level + 1, d)

# Function to print the left view of a given binary tree
def printLeftView(root):

    # create an empty dictionary to store the first node for each level
    d = {}

    # traverse the tree and fill the dictionary
    leftView(root, 1, d)

    # iterate through the dictionary in sorted order of its keys
    # and print the left view
    for i in range(1, len(d) + 1):
        print(d[i], end=' ')

if __name__ == ‘__main__’:

root = Node(1)

root. left = Node(2)
root. right = Node(3)
root. left.right = Node(4)
root. right.left = Node(5)
root. right.right = Node(6)
root. right.left.left = Node(7)
root. right.left.right = Node(8)

printLeftView(root)

Question 28

Print top view of binary tree

Answer 28

Like bottom view and other level order traversal of tree, we use preorder traversal and modify the place that we visited root while we fill out a hashmap. We also need both distance and level as parameter. the hashmap key is distance and the value is a pair of node value and level.

constraine is:
if dist not in d or the current level is less that the level seen so far for that dist
e.g if dist not in d or level < d[dist][1]:

In the second function, we define a dictionary, run the preorder. Then use a for loop on stored(d.keys())

Time and space complexity is O(n)

############ code #########
# Here, the node has `dist` horizontal distance from the tree's root,
# and the level represents the node's level.
def printTop(root, dist, level, d):

    # base case: empty tree
    if root is None:
        return

# if the current level is less than the maximum level seen so far
# for the same horizontal distance, or if the horizontal distance
# is seen for the first time, update the dictionary
if dist not in d or level < d[dist][1]:
    # update value and level for current distance
    d[dist] = (root.key, level)

    # recur for the left subtree by decreasing horizontal distance and
    # increasing level by 1
    printTop(root.left, dist - 1, level + 1, d)

    # recur for the right subtree by increasing both level and
    # horizontal distance by 1
    printTop(root.right, dist + 1, level + 1, d)

# Function to print the top view of a given binary tree
def printTopView(root):

    # create a dictionary where
    # key —> relative horizontal distance of the node from the root node, and
    # value —> pair containing the node's value and its level
    d = {}

    # perform preorder traversal on the tree and fill the dictionary
    printTop(root, 0, 0, d)

    # traverse the dictionary in sorted order of keys and print the top view
    for key in sorted(d.keys()):
        print(d.get(key)[0], end=' ')

Question 29

Find the next node at the same level as the given node in a binary tree

Given a binary tree and a node in it, write an efficient algorithm to find its next node at the same level as the node.

Answer 29

We use iterative level order traversal of a tree.

empty stack --> stack = deque()
add root --> stack.append(root)
while stack:
  size = len(stack)
 while size > 0:
      size -= 1
      front = popleft the node
      then check if front == target:
            then check if size ==0 -----> return None, meaning that there is no right node
            else:   return stack[0]

    append  left and right child if they are xist to the stack

return None

####### code
from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Function to find the next node of a given node in the same level
# in a given binary tree
def findRightNode(root, node):

    # return None if the tree is empty
    if root is None:
        return None

    # create an empty queue and enqueue the root node
    queue = deque()
    queue.append(root)

    # loop till queue is empty
    while queue:

        # calculate the total number of nodes at the current level
        size = len(queue)

        # process every node of the current level and enqueue their
        # non-empty left and right child
        while size > 0:
            size = size - 1
            front = queue.popleft()

        # if the desired node is found, return its next right node
        if front == node:
            # if the next right node doesn't exist, return None
            if size == 0:
                return None

            return queue[0]

        if front.left:
            queue.append(front.left)

        if front.right:
            queue.append(front.right)

return None

Question 30

what is the complete binary tree

Answer 30

A complete binary tree is a binary tree in which every level, except possibly the last, is filled, and all nodes are as far left as possible.

Question 31

check if a binary tree is complete

Answer 31

Array representation of a complete tree
We can solve this problem by using the properties of a complete binary tree. We know that in the array representation of a binary tree,
the left child for a node at index i is present at index 2i+1,
and the right child is present at index 2i+2.

If we construct an array with all the tree elements at the corresponding positions, then the elements will hold consecutive positions for a complete binary tree. If any vacant position is found, then the tree cannot be complete.

For making an array from tree we use in order traversal.
we need to modify is to get , A (a list), i(indext) in addition to root.

and once we visit node we can add root.key. A[i] = root.key

we need one function to count number of nodes
and also one final function which gets (root , size)
then construct the array and we will go through the array and see if we face with False.

###########Code########
# Utility function to calculate the total number of nodes in a binary tree
def size(root):
    if root is None:
        return 0
    return 1 + size(root.left) + size(root.right)

\_\_\_\_\_\_\_\_\_\_\_\_\_
# Perform inorder traversal on the binary tree and fill list `A`
def inorder(root, A, i):

if root is None or i >= len(A):
    return

    # recur with index `2i+1` for left node
    inorder(root.left, A, 2*i + 1)

    # mark index `i` as visited
    A[i] = True # A[i] = root.key

    # recur with index `2i+2` for the right node
    inorder(root.right, A, 2*i + 2)

_______________________

# Function to check if a given binary tree is a complete binary tree or not
def isComplete(root, n):

    # return if the tree is empty
    if root is None:
        return True

    # construct an auxiliary space of size `n`
    A = [False] * n

    # fill list `A`
    inorder(root, A, 0)

# check if all positions in the list are filled or not
for e in A:
    if not e:
        return False

return True

Question 32

convert binary tree to a list with a corresponding position in binary tree

Answer 32

def size(root):
    if root is None:
        return 0
    return 1 + size(root.left) + size(root.right)

# Perform inorder traversal on the binary tree and fill list `A`
def inorder(root, A, i):

if root is None or i >= len(A):
    return

    # recur with index `2i+1` for left node
    inorder(root.left, A, 2*i + 1)

    # mark index `i` as visited
    A[i] = root.key

    # recur with index `2i+2` for the right node
    inorder(root.right, A, 2*i + 2)

# Function to check if a given binary tree is a complete binary tree or not
def convertToList(root, n):

    # return if the tree is empty
    if root is None:
        return True

    # construct an auxiliary space of size `n`
    A = [False] * n

    # fill list `A`
    inorder(root, A, 0)
    print(A)

    # check if all positions in the list are filled or not
    #for e in A:
        #if not e:
            #return False

return True

Question 33

Determine whether the given binary tree nodes are cousins of each other

Answer 33

Two nodes of a binary tree are cousins of each other only if they have different parents, but they are at the same level.

The idea is to search for given nodes in a binary tree by doing inorder traversal on the tree and store their level and parent node. If both nodes are present at the same level and have different parents, they are cousins. If their level is different, or they are a sibling, they cannot be cousins.

Time and space complexity are O(n)

code###########

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# A class to store a binary tree node along with its level and parent information
class NodeInfo:
    def \_\_init\_\_(self, node, level, parent):
        self.node = node
        self.level = level
        self.parent = parent

# Perform inorder traversal on a given binary tree and update 'x' and 'y'
def updateLevelandParent(root, x, y, parent=None, level=1):

    # base case: tree is empty
    if root is None:
        return

    # traverse left subtree
    updateLevelandParent(root.left, x, y, root, level + 1)

    # if the first element is found, save its level and parent node
    if root == x.node:
        x.level = level
        x.parent = parent

    # if the second element is found, save its level and parent node
    if root == y.node:
        y.level = level
        y.parent = parent

    # traverse right subtree
    updateLevelandParent(root.right, x, y, root, level + 1)

# Function to determine if two given nodes are cousins of each other
def checkCousins(root, node1, node2):

    # return if the tree is empty
    if root is None:
        return False

level = 1       # level of the root is 1
parent = None   # parent of the root is None

x = NodeInfo(node1, level, parent)
y = NodeInfo(node2, level, parent)

    # perform inorder traversal on the list and update 'x' and 'y'
    updateLevelandParent(root, x, y)

    # return true if 'x' and 'y' are at the same level, but different parent
    return x.level == y.level and x.parent != y.parent

if __name__ == ‘__main__’:

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. right.right = Node(7)

    if checkCousins(root, root.left.right,  root.right.left):
        print('Nodes are cousins of each other')
    else:
        print('Nodes are not cousins of each other')

Question 34

find the level of a given node

Answer 34

we need three functions:

1) use pre ordet traversal to find the level
2) print all nodes present in that level, which is not a sibling of the node or the node itself.
3) the 3rd function calls the two other functions

The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The program requires O(h) extra space for the call stack, where h is the height of the tree.

code###########

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

# Function to find the level of the given node `x`
def findLevel(root, x, index=1, level=0):

    # return if the tree is empty or level is already found
    if root is None or level != 0:
        return level

    # if the given node is found, update its level
    if root == x:
        level = index

    # recur for the left and right subtree
    level = findLevel(root.left, x, index + 1, level)
    level = findLevel(root.right, x, index + 1, level)

return level

def printLevel(root, node, level):

    # base case
    if root is None:
        return

    # print cousins
    if level == 1:
        print(root.key, end=' ')
        return

# recur for the left and right subtree if the given node
# is not a child of the root
if (not (root.left is not None and root.left == node or
        root.right is not None and root.right == node)):
    printLevel(root.left, node, level - 1)
    printLevel(root.right, node, level - 1)

# Function to print all cousins of a given node
def printAllCousins(root, node):

    # base case
    if not root or root == node:
        return

    # find the level of the given node
    level = findLevel(root, node)

    # print all cousins of the given node using its level number
    printLevel(root, node, level)

Question 35

Function to store postorder traversal on the tree in a list

Answer 35

def postorder(node, list):
    if node is None:
        return

postorder(node.left, list)
postorder(node.right, list)
list.append(node.data)

Question 36

Function to store inorder traversal on the tree in a list

Answer 36

def inorder(node, list):
    if node is None:
        return

inorder(node.left, list)
list.append(node.data)
inorder(node.right, list)

Question 37

Determine whether a binary tree is a subtree of another binary tree
A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T.

Answer 37

we know that inorder and preorder traversal, or inorder and postorder traversal identify a tree uniquely. The idea is to store inorder and postorder traversal of both trees in separate arrays. Then for a given binary tree X to be a subset of another binary tree Y, the inorder traversal of X should be a subset of the inorder traversal of Y. Similarly, the postorder traversal of X should be a subset of the postorder traversal of Y

inorder(X) = {4, 2, 5, 1, 6, 3, 7}
inorder(Y) = {6, 3, 7}

postorder(X) = {4, 5, 2, 6, 7, 3, 1}
postorder(Y) = {6, 7, 3}
Since inorder(Y) is a subset of inorder(X), and postorder(Y) is a subset of postorder(X), we can say that Y is a subtree of X. 

The time complexity of the above solution is O(n2), where n is the total number of nodes in the binary tree. The auxiliary space required by the program is O(n)

########################
# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def \_\_repr\_\_(self):
        return str(self.data)

# Function to store inorder traversal on the tree in a list
def inorder(node, list):
    if node is None:
        return

inorder(node.left, list)
list.append(node.data)
inorder(node.right, list)

# Function to store postorder traversal on the tree in a list
def postorder(node, list):
    if node is None:
        return

postorder(node.left, list)
postorder(node.right, list)
list.append(node.data)

# Utility function to check if y is sublist of x or not
def is_sublist(x, y):
    for i in range(len(x) - len(y) + 1):
        if x[i: i + len(y)] == y:
            return True
    return False

# Function to check if a given binary tree is a subtree of another
# binary tree or not
def checkSubtree(tree, subtree):

    # base case: both trees are the same
    if tree == subtree:
        return True

    # base case: if the first tree is empty but the second tree is non-empty
    if tree is None:
        return False

# store the inorder traversal of both trees in `first` and `second`, respectively
first = []
second = []

inorder(tree, first)
inorder(subtree, second)

    # return false if the second list is not a sublist of the first list
    if not is_sublist(first, second):
        return False

# reset both lists

first. clear()
second. clear()

# Now store postorder traversal of both trees in `first` and `second`, respectively
postorder(tree, first)
postorder(subtree, second)

    # return false if the second list is not a sublist of the first list
    if not is_sublist(first, second):
        return False

return True

Question 38

Find the path from root till node x in binary tree

Answer 38

https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

code

# Finds the path from root node to given root of the tree.
# Stores the path in a list path[], returns true if path
# exists otherwise false
def findPath( root, path, k):

    # Baes Case
    if root is None:
        return False

    # Store this node is path vector. The node will be
    # removed if not in path from root to k
    path.append(root.key)

    # See if the k is same as root's key
    if root.key == k :
        return True

# Check if k is found in left or right sub-tree
if ((root.left != None and findPath(root.left, path, k)) or
        (root.right!= None and findPath(root.right, path, k))):
    return True

    # If not present in subtree rooted with root, remove
    # root from path and return False

path.pop()
return False

Question 39

Lowest Common ancestor of two nodes– using finding path

Answer 39

Following is a simple O(n) algorithm to find LCA of n1 and n2.

1) Find a path from the root to n1 and store it in a vector or array.
2) Find a path from the root to n2 and store it in another vector or array.
3) Traverse both paths till the values in arrays are the same. Return the common element just before the mismatch.

O(N)
############ code

O(n) solution to find LCS of two given values n1 and n2

# A binary tree node
class Node:
    # Constructor to create a new binary node
    def \_\_init\_\_(self, key):
        self.key =  key
        self.left = None
        self.right = None

# Finds the path from root node to given root of the tree.
# Stores the path in a list path[], returns true if path
# exists otherwise false
def findPath( root, path, k):

    # Baes Case
    if root is None:
        return False

    # Store this node is path vector. The node will be
    # removed if not in path from root to k
    path.append(root.key)

    # See if the k is same as root's key
    if root.key == k :
        return True

# Check if k is found in left or right sub-tree
if ((root.left != None and findPath(root.left, path, k)) or
        (root.right!= None and findPath(root.right, path, k))):
    return True

    # If not present in subtree rooted with root, remove
    # root from path and return False

path.pop()
return False

# Returns LCA if node n1 , n2 are present in the given
# binary tree otherwise return -1
def findLCA(root, n1, n2):

# To store paths to n1 and n2 fromthe root
path1 = []
path2 = []

    # Find paths from root to n1 and root to n2.
    # If either n1 or n2 is not present , return -1
    if (not findPath(root, path1, n1) or not findPath(root, path2, n2)):
        return -1

# Compare the paths to get the first different value
i = 0
while(i < len(path1) and i < len(path2)):
    if path1[i] != path2[i]:
        break
    i += 1
return path1[i-1]

# Driver program to test above function
# Let's create the Binary Tree shown in above diagram
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.right.right = Node(7)

print (“LCA(4, 5) = %d” %(findLCA(root, 4, 5,)))
print (“LCA(4, 6) = %d” %(findLCA(root, 4, 6)))
print (“LCA(3, 4) = %d” %(findLCA(root,3,4)))
print (“LCA(2, 4) = %d” %(findLCA(root,2, 4)))

Question 40

Lowest common ancestor - recursive

Answer 40

First we need to check wether the nodes are in the tree.–> is_Node_present
second writ a recursive function to find lca–> findlca
then the third function first –>FindLCA

time O(n), space O(h)
# Function to check if a given node is present in a binary tree or not
def isNodePresent(root, node):

    # base case
    if root is None:
        return False

    # if the node is found, return true
    if root == node:
        return True

    # return true if a given node is found in the left or right subtree
    return isNodePresent(root.left, node) or isNodePresent(root.right, node)

# Function to find the lowest common ancestor of given nodes `x` and `y`, where
# both `x` and `y` are present in a binary tree.
# The function returns true if `x` or `y` is found in a subtree rooted at the root.
# `lca` —> stores `LCA(x, y)`
def findlca(root, lca, x, y):

    # base case 1: return false if the tree is empty
    if root is None:
        return False, lca

    # base case 2: return true if either `x` or `y` is found
    # with lca set to the current node
    if root == x or root == y:
        return True, root

    # recursively check if `x` or `y` exists in the left subtree
    left, lca = findlca(root.left, lca, x, y)

    # recursively check if `x` or `y` exists in the right subtree
    right, lca = findlca(root.right, lca, x, y)

    # if `x` is found in one subtree and `y` is found in the other subtree,
    # update lca to the current node
    if left and right:
        lca = root

    # return true if `x` or `y` is found in either left or right subtree
    return (left or right), lca

# Function to find the lowest common ancestor of nodes `x` and `y`
def findLCA(root, x, y):

    # `lca` stores the lowest common ancestor
    lca = None

    # call LCA procedure only if both `x` and `y` are present in the tree
    if isNodePresent(root, y) and isNodePresent(root, x):
        lca = findlca(root, lca, x, y)[1]

    # if LCA exists, print it
    if lca:
        print('LCA is', lca.data)
    else:
        print('LCA does not exist')

___________

The idea is to traverse the tree starting from the root. If any of the given keys (n1 and n2) matches with the root, then the root is LCA (assuming that both keys are present). If the root doesn’t match with any of the keys, we recur for the left and right subtree. The node which has one key present in its left subtree and the other key present in the right subtree is the LCA. If both keys lie in the left subtree, then the left subtree has LCA also, otherwise, LCA lies in the right subtree.

code

# This function returns pointer to LCA of two given
# values n1 and n2
# This function assumes that n1 and n2 are present in
# Binary Tree
def findLCA(root, n1, n2):

    # Base Case
    if root is None:
        return None

    # If either n1 or n2 matches with root's key, report
    #  the presence by returning root (Note that if a key is
    #  ancestor of other, then the ancestor key becomes LCA
    if root.key == n1 or root.key == n2:
        return root

    # Look for keys in left and right subtrees
    left_lca = findLCA(root.left, n1, n2)
    right_lca = findLCA(root.right, n1, n2)

    # If both of the above calls return Non-NULL, then one key
    # is present in once subtree and other is present in other,
    # So this node is the LCA
    if left_lca and right_lca:
        return root

    # Otherwise check if left subtree or right subtree is LCA
    return left_lca if left_lca is not None else right_lca

Driver program to test above function

# Let us create a binary tree given in the above example
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.right.right = Node(7)
print ("LCA(4,5) = ", findLCA(root, 4, 5).key)
print ("LCA(4,6) = ", findLCA(root, 4, 6).key)
print ("LCA(3,4) = ", findLCA(root, 3, 4).key)
print ("LCA(2,4) = ", findLCA(root, 2, 4).key)

Question 41

write a function to check if a node is leaf node

Answer 41

def is_leaf (root):
             return root.left is None or root.right is None

Question 42

Print all paths from the root to leaf nodes of a binary tree

Given a binary tree, write an efficient algorithm to print all paths from the root node to every leaf node in it.

Answer 42

The idea is to traverse the tree in a preorder fashion and store every encountered node in the current path from the root-to-leaf in a vector. If we encounter a leaf node, print all nodes present in the vector.

so then we need a function for detecting leaf node

code###############

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Function to check if a given node is a leaf node or not
def isLeaf(node):
    return node.left is None and node.right is None

# Recursive function to find paths from the root node to every leaf node
def printRootToLeafPaths(node, path):

    # base case
    if node is None:
        return

    # include the current node to the path
    path.append(node.data)

    # if a leaf node is found, print the path
    if isLeaf(node):
        print(list(path))

    # recur for the left and right subtree
    printRootToLeafPaths(node.left, path)
    printRootToLeafPaths(node.right, path)

    # backtrack: remove the current node after the left, and right subtree are done
    path.pop()

# The main function to print paths from the root node to every leaf node
def printRootToLeafPath(root):

    # list to store root-to-leaf path
    path = deque()
    printRootToLeafPaths(root, path)

if __name__ == ‘__main__’:

    ''' Construct the following tree
              1
            /   \
           /     \
          2       3
         / \     / \
        4   5   6   7
               /     \
              8       9
    '''

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. right.right = Node(7)
root. right.left.left = Node(8)
root. right.right.right = Node(9)

    # print all root-to-leaf paths
    printRootToLeafPath(root)

Question 42

Print all paths from the root to leaf nodes of a binary tree

Given a binary tree, write an efficient algorithm to print all paths from the root node to every leaf node in it.

Answer 42

The idea is to traverse the tree in a preorder fashion and store every encountered node in the current path from the root-to-leaf in a vector. If we encounter a leaf node, print all nodes present in the vector.

so then we need a function for detecting leaf node

code###############

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Function to check if a given node is a leaf node or not
def isLeaf(node):
    return node.left is None and node.right is None

# Recursive function to find paths from the root node to every leaf node
def printRootToLeafPaths(node, path):

    # base case
    if node is None:
        return

    # include the current node to the path
    path.append(node.data)

    # if a leaf node is found, print the path
    if isLeaf(node):
        print(list(path))

    # recur for the left and right subtree
    printRootToLeafPaths(node.left, path)
    printRootToLeafPaths(node.right, path)

    # backtrack: remove the current node after the left, and right subtree are done
    path.pop()

# The main function to print paths from the root node to every leaf node
def printRootToLeafPath(root):

    # list to store root-to-leaf path
    path = deque()
    printRootToLeafPaths(root, path)

if __name__ == ‘__main__’:

    ''' Construct the following tree
              1
            /   \
           /     \
          2       3
         / \     / \
        4   5   6   7
               /     \
              8       9
    '''

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. right.right = Node(7)
root. right.left.left = Node(8)
root. right.right.right = Node(9)

    # print all root-to-leaf paths
    printRootToLeafPath(root)

Question 43

Print all paths from the root to leaf nodes of a binary tree

Given a binary tree, write an efficient algorithm to print all paths from the root node to every leaf node in it.

Answer 43

The idea is to traverse the tree in a preorder fashion and store every encountered node in the current path from the root-to-leaf in a vector. If we encounter a leaf node, print all nodes present in the vector.

so then we need a function for detecting leaf node

code###############

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Function to check if a given node is a leaf node or not
def isLeaf(node):
    return node.left is None and node.right is None

# Recursive function to find paths from the root node to every leaf node
def printRootToLeafPaths(node, path):

    # base case
    if node is None:
        return

    # include the current node to the path
    path.append(node.data)

    # if a leaf node is found, print the path
    if isLeaf(node):
        print(list(path))

    # recur for the left and right subtree
    printRootToLeafPaths(node.left, path)
    printRootToLeafPaths(node.right, path)

    # backtrack: remove the current node after the left, and right subtree are done
    path.pop()

# The main function to print paths from the root node to every leaf node
def printRootToLeafPath(root):

    # list to store root-to-leaf path
    path = deque()
    printRootToLeafPaths(root, path)

if __name__ == ‘__main__’:

    ''' Construct the following tree
              1
            /   \
           /     \
          2       3
         / \     / \
        4   5   6   7
               /     \
              8       9
    '''

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. right.right = Node(7)
root. right.left.left = Node(8)
root. right.right.right = Node(9)

    # print all root-to-leaf paths
    printRootToLeafPath(root)

Question 44

Print all paths from the root to leaf nodes of a binary tree

Given a binary tree, write an efficient algorithm to print all paths from the root node to every leaf node in it.

Answer 44

The idea is to traverse the tree in a preorder fashion and store every encountered node in the current path from the root-to-leaf in a vector. If we encounter a leaf node, print all nodes present in the vector.

so then we need a function for detecting leaf node

code###############

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Function to check if a given node is a leaf node or not
def isLeaf(node):
    return node.left is None and node.right is None

# Recursive function to find paths from the root node to every leaf node
def printRootToLeafPaths(node, path):

    # base case
    if node is None:
        return

    # include the current node to the path
    path.append(node.data)

    # if a leaf node is found, print the path
    if isLeaf(node):
        print(list(path))

    # recur for the left and right subtree
    printRootToLeafPaths(node.left, path)
    printRootToLeafPaths(node.right, path)

    # backtrack: remove the current node after the left, and right subtree are done
    path.pop()

# The main function to print paths from the root node to every leaf node
def printRootToLeafPath(root):

    # list to store root-to-leaf path
    path = deque()
    printRootToLeafPaths(root, path)

if __name__ == ‘__main__’:

    ''' Construct the following tree
              1
            /   \
           /     \
          2       3
         / \     / \
        4   5   6   7
               /     \
              8       9
    '''

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. right.right = Node(7)
root. right.left.left = Node(8)
root. right.right.right = Node(9)

    # print all root-to-leaf paths
    printRootToLeafPath(root)

Question 44

Print all paths from the root to leaf nodes of a binary tree

Given a binary tree, write an efficient algorithm to print all paths from the root node to every leaf node in it.

Answer 44

The idea is to traverse the tree in a preorder fashion and store every encountered node in the current path from the root-to-leaf in a vector. If we encounter a leaf node, print all nodes present in the vector.

so then we need a function for detecting leaf node

code###############

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Function to check if a given node is a leaf node or not
def isLeaf(node):
    return node.left is None and node.right is None

# Recursive function to find paths from the root node to every leaf node
def printRootToLeafPaths(node, path):

    # base case
    if node is None:
        return

    # include the current node to the path
    path.append(node.data)

    # if a leaf node is found, print the path
    if isLeaf(node):
        print(list(path))

    # recur for the left and right subtree
    printRootToLeafPaths(node.left, path)
    printRootToLeafPaths(node.right, path)

    # backtrack: remove the current node after the left, and right subtree are done
    path.pop()

# The main function to print paths from the root node to every leaf node
def printRootToLeafPath(root):

    # list to store root-to-leaf path
    path = deque()
    printRootToLeafPaths(root, path)

if __name__ == ‘__main__’:

    ''' Construct the following tree
              1
            /   \
           /     \
          2       3
         / \     / \
        4   5   6   7
               /     \
              8       9
    '''

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. right.right = Node(7)
root. right.left.left = Node(8)
root. right.right.right = Node(9)

    # print all root-to-leaf paths
    printRootToLeafPath(root)

Question 44

Print all paths from the root to leaf nodes of a binary tree

Given a binary tree, write an efficient algorithm to print all paths from the root node to every leaf node in it.

Answer 44

The idea is to traverse the tree in a preorder fashion and store every encountered node in the current path from the root-to-leaf in a vector. If we encounter a leaf node, print all nodes present in the vector.

so then we need a function for detecting leaf node

code###############

from collections import deque

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Function to check if a given node is a leaf node or not
def isLeaf(node):
    return node.left is None and node.right is None

# Recursive function to find paths from the root node to every leaf node
def printRootToLeafPaths(node, path):

    # base case
    if node is None:
        return

    # include the current node to the path
    path.append(node.data)

    # if a leaf node is found, print the path
    if isLeaf(node):
        print(list(path))

    # recur for the left and right subtree
    printRootToLeafPaths(node.left, path)
    printRootToLeafPaths(node.right, path)

    # backtrack: remove the current node after the left, and right subtree are done
    path.pop()

# The main function to print paths from the root node to every leaf node
def printRootToLeafPath(root):

    # list to store root-to-leaf path
    path = deque()
    printRootToLeafPaths(root, path)

if __name__ == ‘__main__’:

    ''' Construct the following tree
              1
            /   \
           /     \
          2       3
         / \     / \
        4   5   6   7
               /     \
              8       9
    '''

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. right.right = Node(7)
root. right.left.left = Node(8)
root. right.right.right = Node(9)

    # print all root-to-leaf paths
    printRootToLeafPath(root)

Question 45

Find ancestors of a given node in a binary tree

Answer 45

We use the find_path function to make a list of all nodes from root till the given nodes

then we go through the path and print all elements before the index of the given node in the path list.

code###########

def find_path(root, path, a):
    if root is None:
        return False

path.append(root.key)

if root.key ==a:
    return True
if  (root.left != None and find_path(root.left, path, a)) or (
root.right != None and find_path(root.right, path, a)):
    return True

path.pop()
return False

def print_ancestores(root, a):
    path = []
    if find_path(root, path, a):
        n = len(path)
        i = 0 
        lst_idx = 0
        print(path)
        while i

Question 46

Find Level of a given node

Answer 46

def find_level(root, x , level):
    if root is None:
        return -sys.maxsize

if root == x:
    return level

left = find_level(root.left, x , level+1)

if left!= sys.maxsize:
    return left

return find_level(root.right, x , level+1)

Question 47

Find distance between given pairs of nodes in a binary tree

Answer 47

This problem is a standard application of the lowest common ancestor of given nodes. The distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor.

distance(root, x)+distance(root, y)- 2*distance(root,lca)

therefore need 3 functions:

1) find_level(root, x) and find_level(root,y)
2) is_node_available(root, x) and the LCA(root, x,y)
3) writing a function to use the functions and calculate the distance with the formula

The time complexity of the  solution is O(n), where n is the total number of nodes in the binary tree. The program requires O(h) extra space for the call stack, where h is the height of the tree.
########### code

import sys

# A class to store a binary tree node
class Node:
    def \_\_init\_\_(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# Function to check if a given node is present in a binary tree or not
def isNodePresent(root, node):

    # base case
    if root is None:
        return False

    # if the node is found, return true
    if root == node:
        return True

    # return true if the node is found in the left or right subtree
    return isNodePresent(root.left, node) or isNodePresent(root.right, node)

# Function to find the level of a given node present in a binary tree
def findLevel(root, node, level):

    # base case
    if root is None:
        return -sys.maxsize

    # return level if the node is found
    if root == node:
        return level

    # search node in the left subtree
    left = findLevel(root.left, node, level + 1)

    # if the node is found in the left subtree, return the left child
    if left != -sys.maxsize:
        return left

    # otherwise, continue the search in the right subtree
    return findLevel(root.right, node, level + 1)

# Function to find the lowest common ancestor of given nodes `x` and `y`,
# where both `x` and `y` are present in a binary tree.
def findLCA(root, x, y):

    # base case 1: if the tree is empty
    if root is None:
        return None

    # base case 2: if either `x` or `y` is found
    if root == x or root == y:
        return root

    # recursively check if `x` or `y` exists in the left subtree
    left = findLCA(root.left, x, y)

    # recursively check if `x` or `y` exists in the right subtree
    right = findLCA(root.right, x, y)

    # if `x` is found in one subtree and `y` is found in the other subtree,
    # update lca to the current node
    if left and right:
        return root

    # if `x` and `y` exist in the left subtree
    if left:
        return left

    # if `x` and `y` exist in the right subtree
    if right:
        return right

return None

# Function to find the distance between node `x` and node `y` in a
# given binary tree rooted at `root` node
def findDistance(root, x, y):

    # `lca` stores the lowest common ancestor of `x` and `y`
    lca = None

    # call LCA procedure only if both `x` and `y` are present in the tree
    if isNodePresent(root, y) and isNodePresent(root, x):
        lca = findLCA(root, x, y)
    else:
        return -sys.maxsize

    # return distance of `x` from lca + distance of `y` from lca
    return findLevel(lca, x, 0) + findLevel(lca, y, 0)