Question

Implement a recursive program to draw a binary tree so that the root appears at the center of the page, the root of the left subtree is at the center of the left half of the page, etc. Alternative formulation: implement a recursive preorder binary tree traversal so that, when each node is displayed on the page, if the node is a left child it is shown to the left of the node displayed above it, and if it is a right child it is shown to the right of the node displayed above it. There is no requirement that there is a parent-node relationship between nodes displayed on next levels.

Answer 1

binary tree:

A tree is said to be a binary tree if each node of the tree can have maximum of two children. Children of a node of binary tree are ordered. One child is called left child and the other is called right child

Knowledge of tree traversals is very important in order to completely understand Binary Trees. Though the recursive implementation of tree traversals, can be coded very neatly but recursion is generally not preferred.

Creation of Binary Tree Using Recursion

A binary tree can be created recursively. The program will work as follow:

1. Read a data in x.
2. Allocate memory for a new node and store the address in pointer p.
3. Store the data x in the node p.
4. Recursively create the left subtree of p and make it the left child of p.
5. Recursively create the right subtree of p and make it the right child of p.

Given an array arr[] = {15, 10, 20, 8, 12, 16, 25}

        15
     /    \
    10      20
  /   \    /  \ 
  8   12   16  25

 
#include <iostream> 
using namespace std; 

// Structure of the Node of Binary tree 
// with count of Children nodes in 
// left sub-tree and right sub-tree. 
struct Node { 
        int data; 
        int rcount; 
        int lcount; 
        struct Node* left; 
        struct Node* right; 
}; 

// Function to check whether the given 
// Binary tree is a perfect binary tree 
// using the no. of nodes in tree. 
bool isPBT(int count) 
{ 
        count = count + 1; 
        
        // Loop to check the count is in 
        // the form of 2^(n-1) 
        while (count % 2 == 0) 
                count = count / 2; 
        
        if (count == 1) 
                return true; 
        else
                return false; 
} 

// Function to create a new Node 
struct Node* newNode(int data) 
{ 
        struct Node* temp = 
        (struct Node*)malloc( 
                sizeof(struct Node) 
        ); 
        temp->data = data; 
        temp->right = NULL; 
        temp->left = NULL; 
        temp->rcount = 0; 
        temp->lcount = 0; 
} 

// Recursive function to insert 
// elements in a binary tree 
struct Node* insert(struct Node* root, 
                                        int data) 
{ 
        
        // Condition when root is NULL 
        if (root == NULL) { 
                struct Node* n = newNode(data); 
                return n; 
        } 
        
        // Condition when count of left sub-tree 
        // nodes is equal to the count 
        // of right sub-tree nodes 
        if (root->rcount == root->lcount) { 
                root->left = insert(root->left, data); 
                root->lcount += 1; 
        } 
        
        // Condition when count of left sub-tree 
        // nodes is greater than 
        // the right sub-tree nodes 
        else if (root->rcount < root->lcount) { 
                
                // Condition when left Sub-tree is 
                // Perfect Binary Tree then Insert 
                // in right sub-tree. 
                if (isPBT(root->lcount)) { 
                        root->right = insert(root->right, data); 
                        root->rcount += 1; 
                } 
                
                // If Left Sub-tree is not Perfect 
                // Binary Tree then Insert in left sub-tree 
                else { 
                        root->left = insert(root->left, data); 
                        root->lcount += 1; 
                } 
        } 
        return root; 
} 

// Function for inorder Traversal of tree. 
void inorder(struct Node* root) 
{ 
        if (root != NULL) { 
                inorder(root->left); 
                cout << root->data << " "; 
                inorder(root->right); 
        } 
} 

// Driver Code 
int main() 
{ 
        int arr[] = { 8, 6, 7, 12, 5, 1, 9 }; 
        int size = sizeof(arr) / sizeof(int); 
        struct Node* root = NULL; 
        
        // Loop to insert nodes in 
        // Binary Tree in level order 
        for (int i = 0; i < size; i++) 
                root = insert(root, arr[i]); 
        inorder(root); 
        return 0; 
} 

OUTPUT:

12 6 5 8 1 7 9 

Pre Order Traversal:

Pre order is very similar to in order traversal. The way of accessing all the nodes remains the same except the position where we print the node. Now the node is printed/visited before visiting the children of the nodes. Steps are very similar to in-order

> 1. Start with node equal to root node

> 2. Store the node in the stack, print it and visit it's left child.

> 3. Repeat step 2 while node is not NULL, if it's NULL then pop it's parent (i.e. the last node in stack).

> 4. Now move to node's right child and repeat step 2

> 5. Repeat whole procedure while node is not NULL and stack is not empty

#include <bits/stdc++.h> 

using namespace std; 

/* A binary tree node has data, left child and right child */
struct node { 
        int data; 
        struct node* left; 
        struct node* right; 
}; 

/* Helper function that allocates a new node with the given data and 
NULL left and right pointers.*/
struct node* newNode(int data) 
{ 
        struct node* node = new struct node; 
        node->data = data; 
        node->left = NULL; 
        node->right = NULL; 
        return (node); 
} 

// An iterative process to print preorder traversal of Binary tree 
void iterativePreorder(node* root) 
{ 
        // Base Case 
        if (root == NULL) 
                return; 

        // Create an empty stack and push root to it 
        stack<node*> nodeStack; 
        nodeStack.push(root); 

        /* Pop all items one by one. Do following for every popped item 
        a) print it 
        b) push its right child 
        c) push its left child 
        Note that right child is pushed first so that left is processed first */
        while (nodeStack.empty() == false) { 
                // Pop the top item from stack and print it 
                struct node* node = nodeStack.top(); 
                printf("%d ", node->data); 
                nodeStack.pop(); 

                // Push right and left children of the popped node to stack 
                if (node->right) 
                        nodeStack.push(node->right); 
                if (node->left) 
                        nodeStack.push(node->left); 
        } 
} 

// Driver program to test above functions 
int main() 
{ 
        /* Constructed binary tree is 
                        10 
                / \ 
                8        2 
        / \ / 
        3        5 2 
*/
        struct node* root = newNode(10); 
        root->left = newNode(8); 
        root->right = newNode(2); 
        root->left->left = newNode(3); 
        root->left->right = newNode(5); 
        root->right->left = newNode(2); 
        iterativePreorder(root); 
        return 0; 
} 

OUTPUT:

10 8 3 5 2 2

without uisng recursion.

       6
     /    \
    3      5
  /   \     \
 2     5     4
     /   \
    7     4

There are 4 leaves, hence 4 root to leaf paths -
  6->3->2              
  6->3->5->7
  6->3->5->4
  6->5>4

// WITHOUT using recursion 
#include <bits/stdc++.h> 
using namespace std; 

/* A binary tree */
struct Node 
{ 
        int data; 
        struct Node *left, *right; 
}; 

/* Helper function that allocates a new node 
with the given data and NULL left and right 
pointers.*/
Node* newNode(int data) 
{ 
        Node* node = new Node; 
        node->data = data; 
        node->left = node->right = NULL; 
        return node; 
} 

/* Function to print root to leaf path for a leaf 
using parent nodes stored in map */
void printTopToBottomPath(Node* curr, 
                                                map<Node*, Node*> parent) 
{ 
        stack<Node*> stk; 

        // start from leaf node and keep on pushing 
        // nodes into stack till root node is reached 
        while (curr) 
        { 
                stk.push(curr); 
                curr = parent[curr]; 
        } 

        // Start popping nodes from stack and print them 
        while (!stk.empty()) 
        { 
                curr = stk.top(); 
                stk.pop(); 
                cout << curr->data << " "; 
        } 
        cout << endl; 
} 

/* An iterative function to do preorder traversal 
of binary tree and print root to leaf path 
without using recursion */
void printRootToLeaf(Node* root) 
{ 
        // Corner Case 
        if (root == NULL) 
                return; 

        // Create an empty stack and push root to it 
        stack<Node*> nodeStack; 
        nodeStack.push(root); 

        // Create a map to store parent pointers of binary 
        // tree nodes 
        map<Node*, Node*> parent; 

        // parent of root is NULL 
        parent[root] = NULL; 

        /* Pop all items one by one. Do following for 
        every popped item 
                a) push its right child and set its parent 
                pointer 
                b) push its left child and set its parent 
                pointer 
        Note that right child is pushed first so that 
        left is processed first */
        while (!nodeStack.empty()) 
        { 
                // Pop the top item from stack 
                Node* current = nodeStack.top(); 
                nodeStack.pop(); 

                // If leaf node encountered, print Top To 
                // Bottom path 
                if (!(current->left) && !(current->right)) 
                        printTopToBottomPath(current, parent); 

                // Push right & left children of the popped node 
                // to stack. Also set their parent pointer in 
                // the map 
                if (current->right) 
                { 
                        parent[current->right] = current; 
                        nodeStack.push(current->right); 
                } 
                if (current->left) 
                { 
                        parent[current->left] = current; 
                        nodeStack.push(current->left); 
                } 
        } 
} 

// Driver program to test above functions 
int main() 
{ 
        /* Constructed binary tree is 
                10 
                / \ 
        8 2 
        / \ / 
        3        5 2     */
        Node* root = newNode(10); 
        root->left = newNode(8); 
        root->right = newNode(2); 
        root->left->left = newNode(3); 
        root->left->right = newNode(5); 
        root->right->left = newNode(2); 

        printRootToLeaf(root); 

        return 0; 
} 

output:

10 8 3 
10 8 5 
10 2 2