Binary tree - Types and Properties
Tree is sometimes binary tree (BT) and sometimes binary search tree(BST).
BT has maximum of 2 child nodes.
Binary Search Tree or Ordered tree(sometimes) is BT such that left child has value less than the parent and right child has value greater than parent.
Strictly binary tree - If every non-leaf node in BT has non empty left and right subtrees.
A
/ \
B C
/ \
D E
[Read More]
What is a Complete Binary Tree?
A strictly binary tree of depth ’d’ in which all the leaves are at level ’d’ i.e. there is non empty left or right subtrees and leaves are populated at the same level.
In a complete binary tree all the internal nodes have equal degree, which means that one node at the root level, two nodes at level 2, four nodes at level 3, eight nodes at level 4, etc, which the below figure represents:
[Read More]
Binary tree traversal: Preorder, Inorder, Post-order, BFS, DFS, Level Order, zig zag order
In order to illustrate the 3 traversals - pre order, in-order and post-order lets take following tree:
Preorder traversal:
To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10
Implementing pre-order traversal
[Read More]
Construct a full binary tree from a pre-order list of marked nodes
Question: construct a full binary tree from a list of nodes in pre-order. The nodes are marked ‘i’ if they are inner nodes and are marked ‘l’ if they are leaf nodes.
Example given a list of nodes marked as (i, i, i, l, l, i, l, l, i, l, l), we need to construct a tree from those nodes so that the result looks like this:
Notice how all “l” nodes are leaf nodes and “i” nodes are inner nodes?
[Read More]
Convert Binary tree to double linked list in inorder traversal
Problem Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.
Example Input
[Read More]
Convert Binary Tree to Double Linked List in Zig-Zag Order
Question: given a binary tree, write an algorithm to convert the tree into a double-linked list. The list must be as if the tree is traversed in zig-zag and level order.
Solution: let’s first understand what the objective is. By zig-zag level order, the question means that we need to traverse the tree in level order, a.k.a breadth first, such that the next level is traversed in the oposite direction to the current level.
[Read More]
Difference Between Sums of Odd and Even Levels in Binary Trees
Question: calculate the difference between the sum of nodes at even level and sum of nodes at odd level.
Solution: recursion is the easiest way to solve this problem. At each non-null node of the tree, we have three things to do. 1) Find the difference between the node’s left child with it’s children by calling the function recursively on the node’s left child. 2) Do the same thing for the node’s right child.
[Read More]
print the sum( inclusive of the root ) of sub-tree rooted at each node in in-order in Binary Tree
/\*
Two passes with constant space
\*/
int printSum(Tree t, int toPrint)
{
if(t == NULL)
return 0;
int lsum = printSum(t->left, toPrint);
int rsum = printSum(t->right, 0);
int sum = lsum + t->data + rsum;
if(toPrint)
printf("%d ", sum);
printSum(t->right, toPrint);
return sum;
}
/\*
One pass with n space
\*/
int printSum2(Tree t, int a\[\], int \*pos)
{
if(t == NULL)
return 0;
int lsum = printSum2(t->left, a, pos);
(\*pos)++;
int p = \*pos;
int rsum = printSum2(t->right,a, pos);
return a\[p\] = lsum + t->data + rsum;
}
What does flattening list of items into tree means
If I had a list of lists, “flatten” would be the operation that returns a list of all the leaf elements in order, i.e., something that changes:
[[a, b, c], [d, e, f], [g, h i]]
Into
[a, b, c, d, e, f, g, h, i]
For trees, flatting is generating a list of all leaves in natural traversal order (NB: since only leaves are in the result, it doesn’t matter whether you think of this as pre-, in- or post-order traversal.
[Read More]