What is the time complexity of finding the LCA in a Binary Search Tree (BST) in the worst case?
Explanation:
In a balanced BST, we can exploit the sorted property and discard half of the tree at each step, leading to logarithmic time complexity. In the worst case, the BST might be skewed, resembling a linked list, and we might have to traverse all nodes.
Preorder Traversal is often used as a step in which of the following tasks?
Explanation:
The order in which Preorder Traversal visits nodes can be used to reconstruct the original tree. This is helpful in creating a copy where nodes are different entities but maintain the same structure.
Which data structure is used in the iterative implementation of Preorder Traversal?
Explanation:
A stack is used to store the nodes to be processed. We push the right child first, then the left child, ensuring that the left child is processed before the right child when popped.
What is the time complexity of calculating the height of a binary tree?
Explanation:
To calculate the height, we potentially need to visit all nodes in the worst case (e.g., a skewed tree). Hence, the time complexity is O(n), where n is the number of nodes.
Perfect binary trees are commonly used in which of the following applications due to their balanced structure and efficient space utilization?
Explanation:
Heap Sort leverages the balanced nature of (near) perfect binary trees for efficient sorting in O(n log n) time.
Why are two stacks often used in the iterative implementation of Postorder Traversal?
Explanation:
The first stack helps in the general traversal, while the second stack is used to reverse the order in which nodes are processed, effectively giving us the postorder sequence.
What is the time complexity of finding all root-to-leaf paths in a Binary Tree?
Explanation:
In the worst case, we might have a skewed tree where the number of root-to-leaf paths is proportional to the number of nodes. Additionally, each path can have up to O(n) nodes, resulting in quadratic time complexity.
Which of the following types of binary trees guarantees that all levels except possibly the last are completely filled, and the last level has all keys as left as possible?
Explanation:
Complete Binary Trees have a strict structure where all levels are filled except potentially the last one, and nodes are filled from left to right on the last level.
What is the primary advantage of using an iterative approach (with a stack) over recursion for Inorder Traversal?
Explanation:
While both approaches have the same time complexity, recursive calls consume memory on the call stack, which can lead to stack overflow issues for deep trees. Iterative approaches using a stack avoid this problem.
When deleting a node with two children in a BST, which node is typically chosen as its replacement?
Explanation:
To maintain the BST property, the replacement node should be the inorder successor of the deleted node. This is efficiently found as the leftmost child of the right subtree (or the rightmost child of the left subtree, which is equivalent).
Which traversal algorithm is most suitable for finding the Lowest Common Ancestor (LCA) of two nodes in a Binary Tree?
Explanation:
Postorder traversal is most suitable because it processes the left subtree, right subtree, and then the node itself. This allows us to determine if both nodes are present in either subtree before processing the current node.
What is the difference between Postorder and Inorder Traversal?
Explanation:
The key difference lies in the order in which the root node is processed relative to its left and right subtrees.
Which data structure is most suitable for implementing Level Order Traversal efficiently?
Explanation:
A queue's FIFO (First-In, First-Out) property naturally lends itself to Level Order Traversal, as we want to process nodes in the order they are encountered level by level.
What is the time complexity of efficiently finding the diameter of a binary tree?
Explanation:
With an efficient approach (like using DFS to calculate heights along with diameter), you can find the diameter in linear time, O(n), where n is the number of nodes.
When performing a search for a value in a BST, what happens if the value is not found?
Explanation:
If the search value is not present in the BST, the search algorithm typically returns a null pointer or a designated value (like -1) to signal that the value was not found.
Is it possible for a full binary tree to have an even number of nodes?
Explanation:
Full binary trees always have an odd number of nodes due to the relationship between internal nodes and total nodes (2k + 1).
How can you identify leaf nodes during a preorder traversal of a binary tree?
Explanation:
Leaf nodes have no children, so their left and right child pointers will be NULL. Checking these pointers is a reliable way to identify them.
Which data structure is most suitable for efficiently finding a path with a given sum in a Binary Tree?
Explanation:
A stack can be used to keep track of the current path being explored. We can add nodes to the stack as we traverse down the tree and backtrack by popping nodes when we reach a leaf or the sum exceeds the target.
Which type of binary tree is particularly well-suited for representing relationships where each node has exactly two children (e.g., representing expressions in a compiler)?
Explanation:
Full Binary Trees, with their requirement for every node to have either 0 or 2 children, naturally represent binary relationships.
Which of the following statements is true about AVL trees?
Explanation:
AVL trees are self-balancing binary search trees that maintain a balance factor (height difference between left and right subtrees) of -1, 0, or 1 for every node, ensuring a relatively balanced structure.