Category Archives: Tree

Here you will learn about tree data structures.

C program to calculate size of binary tree

Problem statement :

Given a Binary tree write a c program to calculate size of binary tree

Explanation :

Size of Binary tree is defined as total no of nodes in binary tree.

Solution :

Applying recursive approach

if root is NULL then size is zero

else size of left subtree ,right subtree and +1 for the root node.

 

Click here to get binary search tree implementation code.

Find max depth of Binary tree

Problem Statement :

Given a binary tree find the max depth of Binary Tree.

Solution :

Height of binary tree defined as max path length from root to leaf node. if root  is NULL then height is defined as zero. Here we can apply recursive approach as maximum of height of left subtree and right subtree with +1 value of root node .

 

Click here to get binary search tree implementation code.

 

Iterative postorder traversal in BST code in c

As far we have seen iterative inorder traversal in BST using stack. Most traversal are solved using stack in BST. Here iterative postorder traversal in BST also implemented using 2 stacks.

Approach :

Two stacks S1 & S2 

Stack2 (S2) is used only for output purpose only

step 1: push the root in  Stack S1

step2: pop the element from s1  and mark as current node then push into S2

step 3: if popped element has left element then push it into s1

step 4: if popped element has right element then push it into s1

step 5: Follow from step2 to step4 untill stack s1 is emply.

Step 6: Pop out and print the all element from s2

 

Function for iterative postorder traversal :

 

Complete C implementation with BST implementation and iterative postorder traversal  function

 

C program to mirror binary tree

C function to mirror binary tree.

mirror_binary_search_tree

 

C Function implementation :

 

Complete C Code implementation

 

Print Ancestor of given node value in binary tree

Print Ancestor of given node value in binary tree.

For Given Binary Search tree find out the ancestor of a given node value .

Binary Search Tree , 8 is root node ,left branch has nodes whose value are less than 8 and right branch has nodes whose values are greater than 8
Binary Search Tree

 

Node Value                O/P

4                                    8  3  6

13                                8  10  14

 

Recursive function to print ancestor values for given binary search tree.

 

Complete code with binary search tree implementation and ancestor printing function.

 

 

Specific level printing in BST

C code to print specific level values in BST. Level 0 mean Root value.

binary_level

 

For above binary tree
Level          Values

0                       8

1                      3  10

2                     1   6  14

….

Function implementation for level printing :

 

 

Complete C code with implementation of binary tree and level printing in BST.

 

 

Binary Tree implementation with print all paths

Binary Tree implementation code with print all paths in Binary tree Code in C.

 

 

 

Print all paths in Binary Tree

C function to print all paths in binary tree from root to leaf.

For a given binary tree o/p should be :

Binary Search Tree , 8 is root node ,left branch has nodes whose value are less than 8 and right branch has nodes whose values are greater than 8

Print all paths o/p :

8 3 1

8 3 6 4

8 3 6 7

8 10 14 13

 

 

==> Click Here to Get Complete C Code of Binary Search Tree implementation

==> Click here to Get Code for all Path Print and Binary Tree implementation

References : http://cslibrary.stanford.edu/110/BinaryTrees.html

 

Iterative Inorder tree Traversal in BST

Tree traversal are methods to traverse tree in different ways. Tree traversal orders are inorder, preorder, postorder traversal.These traversal can be performed in recursive and iterative ways. When number of nodes in tree are less then we can go for recursive traversal but when we have millions of records then recursive traversal may give stackoverflow. In this situation iterative traversal are useful.

Function definition for iterative inorder tree traversal in BST :

 Complete code implementation of BST with iterative inorder traversal

 

Click here to see recursive tree traversal