#007 DS&A - Trees - TheLazy.Dev

Binary trees are those who have max 2 childs , there are 3 types of binary tree traversal

INORDER - L ROOT R - B A C

PREORDER - ROOT L R - A B C

POSTORDER - L R ROOT - B C A

to write each order , we apply this method . First add dummy edges , start from A and first time you see A write it down , same for B and C. And then for inorder if you see A for second time write it and ....

A B C - first time - PRE

B A C - second time - IN

B C A - third time - POST

Implementation and time complexity

all the implementations are recursive manner so go back to recursive section and fully understand how to visualize it.

// INORDER
struct node
{
    int data;
    struct node *left , *right;
}

void Inorder(struct node* t)
{
    if(t != NULL)
    {
        Inorder(t->left); // 1 
        printf("%c" , t->data); // 2 
        Inorder(t->right); // 3
    }
}

to better understand it go back to recursion visualization and try to trace it

time and space complexity are O(n)

to get the other traversal just change the printf location

Double order traversal

this is nothing but print every node twice (not necessarily successive)

example : abbcac

// INORDER
struct node
{
    int data;
    struct node *left , *right;
}

void DO(struct node* t)
{
    if(t != NULL)
    {
        printf("%c" , t->data); // 1
        DO(t->left); // 2
        printf("%c" , t->data); // 3
        DO(t->right); // 4
    }
}

Triple order

void TO(struct node *t)
{
    if(t)
    {
        printf("%c" , t->data); // 1
        TO(t->left); // 2 
        printf("%c" , t->data); // 3
        TO(t->right); // 4
        printf("%c" , t->data); // 5
    }
}

Indirect recursion on tress

void A(struct node *t)
{
    if(t)
    {
        printf("%c" , t->data); // 1
        B(t->left); // 2
        B(t->right); // 3
    }
}

void B(struct node *t)
{
    if(t)
    {
        A(t->left); //1
        printf("%c" , t->data); // 2
        A(t->right); // 3
    }
}

Number of binary trees possible

if we have 1 node , number of binary tress are 1

if we have 2 node , number of binary tress are 2

if we have 3 node , number of binary tress are 5

the pattern here is(2*n)C(n)/(n+1) c is combinator . so we have here (2*3)C3 / 4 = 6C3 / 4 = 20/4 = 5

but if we need to label nodes (put value for every node) is (2*n)C(n) * n! /(n+1)

construct unique Binary tree

We can construct a unique binary tree using combination between 2 of preorder , inorder and postorder

drawing all the combinations of A,B,C,D,E,F..... is time consuming so we are going to prove it with logic.

let's take IN : 1,2,3,4,5,6,7,8 , PRE: 5,3,1,2,4,6,8,7 , POST = ?

to get POST we need to get a unique Binary search tree.

let's take all the cases of IN - L ROOT R andPRE - ROOT L R where L and R are the subtree respectively to left and right.

this is our INORDER

let's say 5 is the ROOT and in the PRE 5 is also the ROOTand all the elements in the right of it will be the L and R

in the left sub tree1 2 3 4 we look at the PRE we have 3 is the next ROOT

in the right sub tree 6 7 8the PRE it is 6 8 7 so the ROOT is 6 and 8 7 to the right of it

so we have 1 2 in PRE the 2 is to the right of 1 so 2 will fall to the right

for 7 8 in PRE we have 8 is the ROOT and 7 to the left of it

so we form a unique POST binary tree from IN and PRE

if we get the POST of it it's mean print it if it's seen the 3 time.

POST = 2 1 4 3 7 8 6 5

an exercise take POST and IN and form the PRE

Recursive program to count the number of nodes

NN(T) = 1+NN(LST)+NN(RST)and if T is NULL then NN(T)=0

struct node
{
    int i;
    struct node *left , *right;
}

int NN(struct node *t)
{
    if(t)
    {
        int l,r;
        l = NN(t->left); // 1
        r = NN(t->right); // 2
        return (1+l+r); // 3
    }
    else return 0;
}

counting number of leaf

a leaf is a Node with left and right sub trees are NULL

int NL(struct node *t)
{
    if (t == NULL) return 0;
    if(t->left == NULL && t-> right == NULL)
        return 1;
    else
        return (NL(t->left) + NL(t->right));
}

time complexity : O(n)

find the full nodes

full node is the tree who have left and right child

FN(t)   = 0 ; T = NULL
        = 0 ; T is a leaf
        = FN(T->LST) + FN(T->RST); if T has on one child
        = FN(T->LST) + FN(T->RST)+1; if T is full node

int FN(struct node *t)
{
    if(!t) return 0;
    if(!t->left && !t->right) return 0;
    return ( FN(t->left) + FN(t->right)+(t->left && t->right) ) ? 1 : 0;
}

time complexity : O(n)

Recursive program to find the height of a tree

the height is the length of the path to the last leaf you can access

H(t) = {0 ; T is empty
       {0 ; T is a leaf
       {Hmax(H(LST) , H(RST)); otherwise

int H(struct node *t)
{
    if(!t) return 0;
    if( !(t->left) && (!(t->right)) ) return 0;
    int l,r;
    l = H(t->left);
    r = H(t->right);
    return (1+((l>r) ? l : r));
}

Binary search tree

50,15,62,5,20,58,91,3,8,37,60,24

every sub tree in the left is smaller than the root of it and in the right is the higher

INORDER: 3,5,8,15,20,24,37,50,58,60,62,91

so INORDER is nothing but the binary search tree sorted

Binary search tree - POST to IN to PRE

POST ORDER : 10,9,23,22,27,25,15,50,95,60,40,29

we can get directly the INORDER hence is nothing more than the BST sorted

INORDER : 9,10,15,22,23,25,27,29,40,50,60,95

to get that PREORDER we need to draw the tree

the root is 29 since it's the last in the POST , so the root construction is going to be like this , then we go backward 40>29 so it is going to fall to the right and so on..

after we trace it we get PREODER : 29,15,9,10,25,22,23,27,40,60,50,95

Number of BST with 3 Distinct keys

1 2 3

2nCn / n+1 = 6C3 / 4 = 20 / 4 = 5

Identify IN-ORDER , PRE-ORDER and POST-ORDER

1 : M B C A F H P Y K

2: K A M C B Y P F H

3:M B A C K Y F P H

we have those three trees we don't know what is the type of traversal of each one.

K appear first in 2 and last in 1 so it's the ROOT

after drawing the tree we get 1 is POST ,2 is PRE and 3 is IN

Delete a node from BST

if node is a leaf we can delete it , if node is a Non Leaf and one child the child point to the parent of deleted node. If the node have a subtree we replace the greatest element of it.

Examples:

We can delete node 2 without making any changes.
We can delete node 25 and point 27 to 30 instead
If we need to delete node 15 we replace it with 12

Finding minimum and maximum

find_min(struct node *t)
{
    while(t -> left)    t = t -> left;
}

find_max(struct node *t)
{
    while(t -> right)   t = t -> right;
}

Recursive program on testing type of tree

there is arguing on type of trees those are one of their definition , other reference may differ

complete binary is a tree which have 2 or 0 childrens.
full binary tree mean every layer should be node and last row should be leafs

int iscomplete(struct node *t)
{
    if(t == NULL) return 1;
    if(!t->right && !t->left) return 1;
    else if(t->left && t->right) return (iscomplete(t->left) && iscomplete(t->right));
    else return 0;
}

AVL Trees and balancing

AVL tree (named after inventors Adelson-Velsky and Landis) it's the most popular one there is others like (R-B) and (2-3) the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, re-balancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree balancing.

BF = height(LST)-height(RST) the root should be either {-1,0,1} else we rotated . If it is left-unbalance we rotate it clock wise else opposite clock wise.

the root is 2 != {-1,0,1} so it's not balanced , and it's left unbalanced so we need to rotate CW

now the root is 0 so now it's balanced.

constructing AVL trees and time complexity

50 , 20 , 60 ,10 , 8 , 15 , 32 ,46 , 11 , 48

go clock wise

now rotate Anti Clock wise

now it's Left-Left so we rotate CW and so on we continue and in the end we get this tree

	BST	Balanced BST
search	O(n)	O( log n )
height	O(n)	O( log n )
Insertion	O(n)	O(log n)

it's O(log n) because the height is smaller

Minimum and Maximum nodes in AVL tree

S(h) = S(h-1) + S(h-2) + 1

S(1) = 0
S(2) = 1

So let's say h = 6, then S(h = 6) will be (just replacing):

S(6) = S(6-1) + S(6-2) + 1
S(6) = S(5) + S(4) + 1 
S(6) = 2*S(4) + S(3) + 1 + 1
S(6) = 2*(S(3) + S(2) + 1) + S(3) + 2
S(6) = 3*S(3) + 2*S(2) + 4
S(6) = 3*(S(2) + S(1) + 1) + 2*S(2) + 4
S(6) = 5*S(2) + 3*S(1) + 7
S(6) = 5*1 + 3*0 + 7
S(6) = 12

Expression trees

a+b take this and let's draw the tree

PRE : +ab
IN  : a+b
POST: ab+

a+b*c

PRE : +a*bc
IN  : a+b*c
POST: abc*+

Various tree representations

The method we see is a pointer to the left and right child , what if we have like 10 childs?

There is a representation called LCRS (Left Child Right Sibling)

LC = 2*i
RC = 2*i+1
Parent = x/2

because it's binary tree multiplying by 2 is nothing but shifting by 1 bit.

if we have i = 2 (base 10) = 10 (base 2) , 2*i = 100 and 2*i+1 = 101 , same for divining by 2 in binary 100/2 = 10

another representation is like this

(Root (a b c) (d e f) ) where (a b c) is LSB of Root and (d e f) is RSB of Root and a is root of LSB and b is left leaf and c is right leaf , same for d e f

Blog

#007 DS&A - Trees

Omar