BinaryTrees

Question 1

Iterative pattern of pre-order traversal?

Answer 1

1. Push to the stack
2. Pop top
3. Retrieve uninvited neighbors of top and push them to the stack
4. Repeat 1,2,3 while stack not empty

Question 2

What is the iterative in-order traversal of binary tree?

Answer 2

Node curr = n;
Stack stk = new Stack();
while (curr != null || stk.Count != 0)
 {
      while (curr != null)
      {
        stk.Push(curr);
        curr = curr.left;
      }
      curr = stk.Pop();
      curr = curr.right;
 }

Question 3

Which BST traversal gives ordered resultset?

Answer 3

InOrder traversal

Question 4

What is the rooted tree?

Answer 4

a tree with a designated root node.

Question 5

Pseudo Code for level order traversal(left to right) of binary tree

Answer 5

1. Push root to the queue
2. While(queue.Count!=0)
   Take queue elements count
   While(count!=0)
   Dequeue element from the queue
   Add dequeue element to list
   If dequeue element.left !=null
   Push left element to the queue
   If dequeue element.right!=null
   Push right element to the queue

Question 6

Pseudo to find the successor of node in binary search tree?

Answer 6

public int successor(TreeNode root) {
  root = root.right;
  while (root.left != null) root = root.left;
  return root;
}

Question 7

Pseudo to find the predecessor of node in binary search tree?

Answer 7

public int predecessor(TreeNode root) {
  root = root.left;
  while (root.right != null) root = root.right;
  return root;
}

Question 8

How many edges the tree have with n nodes?

Answer 8

n-1 .

Number of edges are always one less than number of nodes in the graph.

Question 9

How to find the tree diameter ?

Answer 9

private int DiameterOfBinaryTree2(TreeNode root, ResultWrapper wrapper)
{
if (root == null)
return 0;

        int left = DiameterOfBinaryTree2(root.left, wrapper);
        int right = DiameterOfBinaryTree2(root.right, wrapper);

        int leftMax = 0;
        int rightMax = 0;

            if (root.left != null)
            {
                leftMax = 1 + left;
            }
            if (root.right != null)
            {
                rightMax = 1 + right;
            }

        wrapper.Result = Math.Max(wrapper.Result, leftMax + rightMax);

        return Math.Max(leftMax, rightMax);
    }

Question 10

How to find out that tree is Valid BST?

Answer 10

private bool Helper(TreeNode node, long left, long right)
{
if (node == null)
return true;
return node.val > left && node.val < right &&
Helper(node.left, left, node.val) &&
Helper(node.right, node.val, right);
}

Question 11

What is the difference between full binary tree vs complete tree?

Answer 11

https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/

Full Binary Tree A Binary Tree is a full binary tree if every node has 0 or 2 children.
A Binary Tree is a complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible

Question 12

What is red-black tree and its time complexity?

Answer 12

https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/
A red-black tree is a kind of self-balancing binary search tree. It does search/insert/delete in O(n) time