MiQ Digital SDE Interview Questions and Answers

A binary tree with 4 internal nodes has 5 leaf nodes.

• A binary tree with n internal nodes has n+1 leaf nodes.

• A leaf node is a node with no children.

• Count the number of leaf nodes to find the answer.

The number of swaps required to sort an array using bubblesort

• Bubble sort compares adjacent elements and swaps them if they are in the wrong order

• Count the number of swaps required to sort the given array

• The given array requires 19 swaps to be sorted using bubblesort

Given preorder and postorder traversal, find inorder traversal of a binary tree.

• The last element of postorder traversal is the root of the tree

• Find the root in preorder traversal and divide the tree into left and right subtrees

• Recursively find the inorder traversal of left and right subtrees

• Combine the inorder traversal of left subtree, root, and inorder traversal of right subtree