Recursive Program to Print extreme nodes of each level of Binary Tree in alternate order

0 0 11 minutes read

Given a binary tree, the task is to print nodes of extreme corners of each level but in alternate order.
Examples:

Input : 
         1
        /  \
       2    3
      /    /  \
     4    5    6
    /    / \
   7    8   9
Output : 1 2 6 7
Print the rightmost node at 1st level: 1
Print the leftmost node at 2nd level: 2
Print the rightmost node at 3rd level: 6
Print the leftmost node at 4th level: 7
Other possible output will be -> 1 3 4 9

Input :
        3 
       /  \
      8    1
     / \  / \
    9  5 6   4
Output : 3 8 4

We have already discussed the iterative approach to solve this problem. In this post the recursive approach is discussed.
Approach: The idea is to perform level order traversal in the spiral form and at each level print the first node during the traversal, these will be the nodes at extreme corner present in the alternate form.
Below is the implementation of the above approach:

C++

// C++ program to print nodes of extreme corners
// of each level in alternate order
 
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree node
struct Node {
    int data;
    Node *left, *right;
};
 
// Utility function to allocate memory for a new node
Node* newNode(int data)
{
    Node* node = new (Node);
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
 
// Function that returns the height of the binary tree
int height(Node* root)
{
    if (root == NULL)
        return 0;
 
    int lheight = height(root->left);
    int rheight = height(root->right);
 
    return max(lheight, rheight) + 1;
}
 
// Function performs level order traversal from right to
// left and prints the first node during the traversal
void rightToLeft(Node* root, int level, int& f)
{
    if (root == NULL)
        return;
 
    // Checks for the value of f so that
    // only first node is printed during
    // the traversal and no other node is printed
    if (level == 1 && f == 0) {
        printf("%d ", root->data);
        f = 1;
    }
 
    else if (level > 1) {
        rightToLeft(root->right, level - 1, f);
        rightToLeft(root->left, level - 1, f);
    }
}
 
// Function performs level order traversal from left to
// right and prints the first node during the traversal
void leftToRight(Node* root, int level, int& f)
{
    if (root == NULL)
        return;
 
    // Checks for the value of f so that
    // only first node is printed during
    // the traversal and no other node is printed
    if (level == 1 && f == 1) {
        printf("%d ", root->data);
        f = 0;
    }
 
    else if (level > 1) {
        leftToRight(root->left, level - 1, f);
        leftToRight(root->right, level - 1, f);
    }
}
 
// Function to print the extreme nodes of
// a given binary tree
void printExtremeNodes(Node* root)
{
    // Stores height of binary tree
    int h = height(root);
 
    // Flag to mark the change in level
    int flag = 0;
 
    // To check if the extreme node of a
    // particular level has been visited
    int f = 0;
 
    for (int i = 1; i <= h; i++) {
        // If flag is zero then traverse from
        // right to left at the given level and
        // print the first node during the traversal
        if (flag == 0) {
            rightToLeft(root, i, f);
            flag = 1;
        }
 
        // If flag is one then traverse from
        // left to right at the given level and
        // print the first node during the traversal
        else if (flag == 1) {
            leftToRight(root, i, f);
            flag = 0;
        }
    }
 
    return;
}
 
// Driver code
int main()
{
    Node* root = newNode(1);
 
    root->left = newNode(2);
    root->right = newNode(3);
 
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->right = newNode(7);
 
    root->left->left->left = newNode(8);
    root->left->left->right = newNode(9);
    root->left->right->left = newNode(10);
    root->left->right->right = newNode(11);
    root->right->right->left = newNode(14);
    root->right->right->right = newNode(15);
 
    root->left->left->left->left = newNode(16);
    root->left->left->left->right = newNode(17);
    root->right->right->right->right = newNode(31);
 
    printExtremeNodes(root);
 
    return 0;
}

Java

// Java program to print nodes of extreme corners 
// of each level in alternate order 
import java.util.*;
 
class GFG
{
     
//INT class
static class INT
{
    int a;
}
 
// A binary tree node 
static class Node 
{ 
    int data; 
    Node left, right; 
}; 
 
// Utility function to allocate memory for a new node 
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
 
// Function that returns the height of the binary tree 
static int height(Node root) 
{ 
    if (root == null) 
        return 0; 
 
    int lheight = height(root.left); 
    int rheight = height(root.right); 
 
    return Math.max(lheight, rheight) + 1; 
} 
 
// Function performs level order traversal from right to 
// left and prints the first node during the traversal 
static void rightToLeft(Node root, int level, INT f) 
{ 
    if (root == null) 
        return; 
 
    // Checks for the value of f so that 
    // only first node is printed during 
    // the traversal and no other node is printed 
    if (level == 1 && f.a == 0) 
    { 
        System.out.printf("%d ", root.data); 
        f.a = 1; 
    } 
 
    else if (level > 1) 
    { 
        rightToLeft(root.right, level - 1, f); 
        rightToLeft(root.left, level - 1, f); 
    } 
} 
 
// Function performs level order traversal from left to 
// right and prints the first node during the traversal 
static void leftToRight(Node root, int level, INT f) 
{ 
    if (root == null) 
        return; 
 
    // Checks for the value of f so that 
    // only first node is printed during 
    // the traversal and no other node is printed 
    if (level == 1 && f.a == 1) 
    { 
        System.out.printf("%d ", root.data); 
        f.a = 0; 
    } 
 
    else if (level > 1)
    { 
        leftToRight(root.left, level - 1, f); 
        leftToRight(root.right, level - 1, f); 
    } 
} 
 
// Function to print the extreme nodes of 
// a given binary tree 
static void printExtremeNodes(Node root) 
{ 
    // Stores height of binary tree 
    int h = height(root); 
 
    // Flag to mark the change in level 
    int flag = 0; 
 
    // To check if the extreme node of a 
    // particular level has been visited 
    INT f=new INT();
    f.a = 0; 
 
    for (int i = 1; i <= h; i++) 
    { 
        // If flag is zero then traverse from 
        // right to left at the given level and 
        // print the first node during the traversal 
        if (flag == 0)
        { 
            rightToLeft(root, i, f); 
            flag = 1; 
        } 
 
        // If flag is one then traverse from 
        // left to right at the given level and 
        // print the first node during the traversal 
        else if (flag == 1) 
        { 
            leftToRight(root, i, f); 
            flag = 0; 
        } 
    } 
 
    return; 
} 
 
// Driver code 
public static void main(String args[])
{ 
    Node root = newNode(1); 
 
    root.left = newNode(2); 
    root.right = newNode(3); 
 
    root.left.left = newNode(4); 
    root.left.right = newNode(5); 
    root.right.right = newNode(7); 
 
    root.left.left.left = newNode(8); 
    root.left.left.right = newNode(9); 
    root.left.right.left = newNode(10); 
    root.left.right.right = newNode(11); 
    root.right.right.left = newNode(14); 
    root.right.right.right = newNode(15); 
 
    root.left.left.left.left = newNode(16); 
    root.left.left.left.right = newNode(17); 
    root.right.right.right.right = newNode(31); 
 
    printExtremeNodes(root); 
 
} 
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to print nodes of 
# extreme corners of each level in 
# alternate order
from collections import deque
 
# A binary tree node has key, pointer to left
# child and a pointer to right child
class Node:
    def __init__(self, key):
         
        self.data = key
        self.left = None
        self.right = None
 
# Function that returns the height of
# the binary tree
def height(root: Node) -> int:
 
    if (root is None):
        return 0
 
    lheight = height(root.left)
    rheight = height(root.right)
 
    return max(lheight, rheight) + 1
 
# Function performs level order traversal 
# from right to left and prints the first
# node during the traversal
def rightToLeft(root: Node, level: int) -> int:
     
    global f
 
    if (root is None):
        return
 
    # Checks for the value of f so that
    # only first node is printed during
    # the traversal and no other node is printed
    if (level == 1 and f == 0):
        print("%d " % root.data, end = "")
        f = 1
 
    elif (level > 1):
        rightToLeft(root.right, level - 1)
        rightToLeft(root.left, level - 1)
 
# Function performs level order traversal 
# from left to right and prints the first 
# node during the traversal
def leftToRight(root: Node, level: int):
     
    global f
 
    if (root is None):
        return
 
    # Checks for the value of f so that
    # only first node is printed during
    # the traversal and no other node is printed
    if (level == 1 and f == 1):
        print("%d " % root.data, end = "")
        f = 0
 
    elif (level > 1):
        leftToRight(root.left, level - 1)
        leftToRight(root.right, level - 1)
 
# Function to print the extreme nodes of
# a given binary tree
def printExtremeNodes(root: Node):
     
    global f
 
    # Stores height of binary tree
    h = height(root)
 
    # Flag to mark the change in level
    flag = 0
 
    # To check if the extreme node of a
    # particular level has been visited
    f = 0
 
    for i in range(1, h + 1):
         
        # If flag is zero then traverse from
        # right to left at the given level and
        # print the first node during the traversal
        if (flag == 0):
            rightToLeft(root, i)
            flag = 1
 
        # If flag is one then traverse from
        # left to right at the given level and
        # print the first node during the traversal
        elif (flag == 1):
            leftToRight(root, i)
            flag = 0
 
    return
 
# Driver Code
if __name__ == "__main__":
     
    root = Node(1)
 
    root.left = Node(2)
    root.right = Node(3)
 
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.right = Node(7)
 
    root.left.left.left = Node(8)
    root.left.left.right = Node(9)
    root.left.right.left = Node(10)
    root.left.right.right = Node(11)
    root.right.right.left = Node(14)
    root.right.right.right = Node(15)
 
    root.left.left.left.left = Node(16)
    root.left.left.left.right = Node(17)
    root.right.right.right.right = Node(31)
 
    printExtremeNodes(root)
 
# This code is contributed by sanjeev2552

C#

// C# program to print nodes of extreme corners 
// of each level in alternate order 
using System;
 
class GFG
{
     
//INT class
public class INT
{
    public int a;
}
 
// A binary tree node 
public class Node 
{ 
    public int data; 
    public Node left, right; 
}; 
 
// Utility function to allocate memory for a new node 
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
 
// Function that returns the height of the binary tree 
static int height(Node root) 
{ 
    if (root == null) 
        return 0; 
 
    int lheight = height(root.left); 
    int rheight = height(root.right); 
 
    return Math.Max(lheight, rheight) + 1; 
} 
 
// Function performs level order traversal from right to 
// left and prints the first node during the traversal 
static void rightToLeft(Node root, int level, INT f) 
{ 
    if (root == null) 
        return; 
 
    // Checks for the value of f so that 
    // only first node is printed during 
    // the traversal and no other node is printed 
    if (level == 1 && f.a == 0) 
    { 
        Console.Write("{0} ", root.data); 
        f.a = 1; 
    } 
 
    else if (level > 1) 
    { 
        rightToLeft(root.right, level - 1, f); 
        rightToLeft(root.left, level - 1, f); 
    } 
} 
 
// Function performs level order traversal from left to 
// right and prints the first node during the traversal 
static void leftToRight(Node root, int level, INT f) 
{ 
    if (root == null) 
        return; 
 
    // Checks for the value of f so that 
    // only first node is printed during 
    // the traversal and no other node is printed 
    if (level == 1 && f.a == 1) 
    { 
        Console.Write("{0} ", root.data); 
        f.a = 0; 
    } 
 
    else if (level > 1)
    { 
        leftToRight(root.left, level - 1, f); 
        leftToRight(root.right, level - 1, f); 
    } 
} 
 
// Function to print the extreme nodes of 
// a given binary tree 
static void printExtremeNodes(Node root) 
{ 
    // Stores height of binary tree 
    int h = height(root); 
 
    // Flag to mark the change in level 
    int flag = 0; 
 
    // To check if the extreme node of a 
    // particular level has been visited 
    INT f=new INT();
    f.a = 0; 
 
    for (int i = 1; i <= h; i++) 
    { 
        // If flag is zero then traverse from 
        // right to left at the given level and 
        // print the first node during the traversal 
        if (flag == 0)
        { 
            rightToLeft(root, i, f); 
            flag = 1; 
        } 
 
        // If flag is one then traverse from 
        // left to right at the given level and 
        // print the first node during the traversal 
        else if (flag == 1) 
        { 
            leftToRight(root, i, f); 
            flag = 0; 
        } 
    } 
 
    return; 
} 
 
// Driver code 
public static void Main()
{ 
    Node root = newNode(1); 
 
    root.left = newNode(2); 
    root.right = newNode(3); 
 
    root.left.left = newNode(4); 
    root.left.right = newNode(5); 
    root.right.right = newNode(7); 
 
    root.left.left.left = newNode(8); 
    root.left.left.right = newNode(9); 
    root.left.right.left = newNode(10); 
    root.left.right.right = newNode(11); 
    root.right.right.left = newNode(14); 
    root.right.right.right = newNode(15); 
 
    root.left.left.left.left = newNode(16); 
    root.left.left.left.right = newNode(17); 
    root.right.right.right.right = newNode(31); 
 
    printExtremeNodes(root); 
 
} 
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
 
// JavaScript program to print nodes of extreme corners 
// of each level in alternate order 
     
//INT class
class INT
{
    constructor()
    {
        this.a = 0;
    }
}
 
// A binary tree node 
class Node 
{ 
    constructor()
    {
        this.data = 0;
        this.left = null;
        this.right = null;
    }
}; 
 
// Utility function to allocate memory for a new node 
function newNode(data) 
{ 
    var node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
 
// Function that returns the height of the binary tree 
function height(root) 
{ 
    if (root == null) 
        return 0; 
 
    var lheight = height(root.left); 
    var rheight = height(root.right); 
 
    return Math.max(lheight, rheight) + 1; 
} 
 
// Function performs level order traversal from right to 
// left and prints the first node during the traversal 
function rightToLeft(root, level, f) 
{ 
    if (root == null) 
        return; 
 
    // Checks for the value of f so that 
    // only first node is printed during 
    // the traversal and no other node is printed 
    if (level == 1 && f.a == 0) 
    { 
        document.write(root.data + " "); 
        f.a = 1; 
    } 
 
    else if (level > 1) 
    { 
        rightToLeft(root.right, level - 1, f); 
        rightToLeft(root.left, level - 1, f); 
    } 
} 
 
// Function performs level order traversal from left to 
// right and prints the first node during the traversal 
function leftToRight(root, level, f) 
{ 
    if (root == null) 
        return; 
 
    // Checks for the value of f so that 
    // only first node is printed during 
    // the traversal and no other node is printed 
    if (level == 1 && f.a == 1) 
    { 
        document.write(root.data+ " "); 
        f.a = 0; 
    } 
 
    else if (level > 1)
    { 
        leftToRight(root.left, level - 1, f); 
        leftToRight(root.right, level - 1, f); 
    } 
} 
 
// Function to print the extreme nodes of 
// a given binary tree 
function printExtremeNodes(root) 
{ 
    // Stores height of binary tree 
    var h = height(root); 
 
    // Flag to mark the change in level 
    var flag = 0; 
 
    // To check if the extreme node of a 
    // particular level has been visited 
    var f=new INT();
    f.a = 0; 
 
    for (var i = 1; i <= h; i++) 
    { 
        // If flag is zero then traverse from 
        // right to left at the given level and 
        // print the first node during the traversal 
        if (flag == 0)
        { 
            rightToLeft(root, i, f); 
            flag = 1; 
        } 
 
        // If flag is one then traverse from 
        // left to right at the given level and 
        // print the first node during the traversal 
        else if (flag == 1) 
        { 
            leftToRight(root, i, f); 
            flag = 0; 
        } 
    } 
 
    return; 
} 
 
// Driver code 
var root = newNode(1); 
root.left = newNode(2); 
root.right = newNode(3); 
root.left.left = newNode(4); 
root.left.right = newNode(5); 
root.right.right = newNode(7); 
root.left.left.left = newNode(8); 
root.left.left.right = newNode(9); 
root.left.right.left = newNode(10); 
root.left.right.right = newNode(11); 
root.right.right.left = newNode(14); 
root.right.right.right = newNode(15); 
root.left.left.left.left = newNode(16); 
root.left.left.left.right = newNode(17); 
root.right.right.right.right = newNode(31); 
printExtremeNodes(root); 
 
 
</script>

Output:

1 2 7 8 31

Time Complexity: O(N^2), where N is the total number of nodes in the binary tree.
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!