Binary Tree: You are given a binary tree, you need to print the extreme nodes in alternate order.

Problem Statement:

You are given a binary tree, you need to print the extreme nodes in alternate order.

Example:

Input:

Output:

7 6

Solution Explanation:

We will do BSF or level order traversal using queue DS.

Then for each level print the extreme right or left node.

If the level of binary tree is odd, then print the extreme left node else print the extreme right node.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Node 
{
    int data;
    struct Node *left;
    struct Node *right;
};


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_inorder(Node* root)
{
    if (root == NULL)
        return;

    display_inorder(root->left);
    cout << root->data << " ";
    display_inorder(root->right);
}


void insert_inorder(Node* root, vector<int>& nodes) 
{
    if (root == nullptr) 
    {
        return;
    }
  
    insert_inorder(root->left, nodes);  
    nodes.push_back(root->data);          
    insert_inorder(root->right, nodes); 
}

void solution(Node* root)
{
    // Store nodes of each level
    queue<Node*> q;
    q.push(root);

    while (!q.empty()) 
    {

        int n = q.size();

        //print the alternate nodes
        for (int i = 0; i < n; i++) 
        {
            Node* temp = q.front();
            q.pop();

            if (i % 2 == 0) 
            {
                cout << temp->data << " ";
            }

            if (temp->left) 
            {
                q.push(temp->left);
            }

            if (temp->right) 
            {
                q.push(temp->right);
            }
        }
        cout << endl;
    }
}

int main(void)
{
    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(12);
    root->left->left = newNode(2);
    root->left->right = newNode(9);
    root->right->left = newNode(11);
    root->right->right = newNode(14);

    solution(root);
    
    return 0;
}

Output

10
8