Skip to main content

Print binary tree levels in ascending order

Given binary tree which include integer values. Our goal is to print level by level node in sorted order. Assume that unique element present in level order.

Ascending level order view

Here given code implementation process.

import java.util.HashMap;
import java.util.HashSet;
// Java Program 
// Print binary tree levels in ascending order

// Binary Tree node
class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        // Set initial value
        this.root = null;
    }
    public void levelNodes(HashMap < Integer, 
                            HashSet < Integer >> record, 
                            TreeNode track, int level)
    {
        if (track != null)
        {
            if (!record.containsKey(level))
            {
                record.put(level, new HashSet < Integer > ());
            }
            record.get(level).add(track.data);
            // Visit left subtree
            levelNodes(record, track.left, level + 1);
            // Visit right subtree
            levelNodes(record, track.right, level + 1);
        }
    }
    // Display sorted nodes by level
    public void showSortedNode()
    {
        if (this.root == null)
        {
            return;
        }
        HashMap < Integer, HashSet < Integer >> record = 
          new HashMap < Integer, HashSet < Integer >> ();
        this.levelNodes(record, this.root, 1);
        // Get number of level
        int n = record.size();
        for (int i = 1; i <= n; ++i)
        {
            // Print level nodes
            for (int v: record.get(i))
            {
                System.out.print("  " + v);
            }
            System.out.print("\n");
        }
    }
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        /*   
            Binary Tree
        -----------------------
                 10
               /    \
              11     5
             / \    /  \
            1   3  7    2
               / \  \    \
              9  -1  8    4
        ----------------------           
        */
        tree.root = new TreeNode(10);
        tree.root.left = new TreeNode(11);
        tree.root.right = new TreeNode(5);
        tree.root.right.right = new TreeNode(2);
        tree.root.right.right.right = new TreeNode(4);
        tree.root.right.left = new TreeNode(7);
        tree.root.right.left.right = new TreeNode(8);
        tree.root.left.left = new TreeNode(1);
        tree.root.left.right = new TreeNode(3);
        tree.root.left.right.left = new TreeNode(9);
        tree.root.left.right.right = new TreeNode(-1);
        tree.showSortedNode();
    }
}

Output

  10
  5  11
  1  2  3  7
  -1  4  8  9
// Include header file
#include <iostream>
#include <set>
#include <unordered_map>

using namespace std;
// C++ Program 
// Print binary tree levels in ascending order

// Binary Tree node
class TreeNode
{
    public: 
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        // Set node value
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
class BinaryTree
{
    public: TreeNode *root;
    BinaryTree()
    {
        this->root = NULL;
    }
    void levelNodes(unordered_map < int, set < int > > &record, 
                    TreeNode *track, int level)
    {
        if (track != NULL)
        {
            
            record[level].insert(track->data);
            // Visit left subtree
            this->levelNodes(record, track->left, level + 1);
            // Visit right subtree
            this->levelNodes(record, track->right, level + 1);
        }
    }
    // Display sorted nodes by level
    void showSortedNode()
    {
        if (this->root == NULL)
        {
            return;
        }
        unordered_map < int, set < int > > record;
        this->levelNodes(record, this->root, 1);
        // Get number of level
        int n = record.size();
        for (int i = 1; i <= n; ++i)
        {
            // Print level nodes
            for (auto &v: record[i])
            {
                cout << "  " << v;
            }
            cout << "\n";
        }
    }
};
int main()
{
    BinaryTree *tree = new BinaryTree();
    /* 
                Binary Tree
            -----------------------
                     10
                   /    \
                  11     5
                 / \    /  \
                1   3  7    2
                   / \  \    \
                  9  -1  8    4
            ----------------------           
            */
    tree->root = new TreeNode(10);
    tree->root->left = new TreeNode(11);
    tree->root->right = new TreeNode(5);
    tree->root->right->right = new TreeNode(2);
    tree->root->right->right->right = new TreeNode(4);
    tree->root->right->left = new TreeNode(7);
    tree->root->right->left->right = new TreeNode(8);
    tree->root->left->left = new TreeNode(1);
    tree->root->left->right = new TreeNode(3);
    tree->root->left->right->left = new TreeNode(9);
    tree->root->left->right->right = new TreeNode(-1);
    tree->showSortedNode();
    return 0;
}

Output

  10
  5  11
  1  2  3  7
  -1  4  8  9
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp Program 
// Print binary tree levels in ascending order

// Binary Tree node
public class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        // Set initial value
        this.root = null;
    }
    public void levelNodes(Dictionary < int, SortedSet < int > > record, 
                            TreeNode track, int level)
    {
        if (track != null)
        {
            if (!record.ContainsKey(level))
            {
                record.Add(level, new SortedSet < int > ());
            }
            record[level].Add(track.data);
            // Visit left subtree
            this.levelNodes(record, track.left, level + 1);
            // Visit right subtree
            this.levelNodes(record, track.right, level + 1);
        }
    }
    // Display sorted nodes by level
    public void showSortedNode()
    {
        if (this.root == null)
        {
            return;
        }
        Dictionary < int, SortedSet < int > > record = 
          new Dictionary < int, SortedSet < int > > ();
        this.levelNodes(record, this.root, 1);
        // Get number of level
        int n = record.Count;
        for (int i = 1; i <= n; ++i)
        {
            // Print level nodes
            foreach(int v in record[i])
            {
                Console.Write("  " + v);
            }
            Console.Write("\n");
        }
    }
    public static void Main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        /*   
            Binary Tree
            -----------------------
                     10
                   /    \
                  11     5
                 / \    /  \
                1   3  7    2
                   / \  \    \
                  9  -1  8    4
            ----------------------           
        */
        tree.root = new TreeNode(10);
        tree.root.left = new TreeNode(11);
        tree.root.right = new TreeNode(5);
        tree.root.right.right = new TreeNode(2);
        tree.root.right.right.right = new TreeNode(4);
        tree.root.right.left = new TreeNode(7);
        tree.root.right.left.right = new TreeNode(8);
        tree.root.left.left = new TreeNode(1);
        tree.root.left.right = new TreeNode(3);
        tree.root.left.right.left = new TreeNode(9);
        tree.root.left.right.right = new TreeNode(-1);
        tree.showSortedNode();
    }
}

Output

  10
  5  11
  1  2  3  7
  -1  4  8  9
<?php
// Php Program
// Print binary tree levels in ascending order

// Binary Tree node
class TreeNode
{
    public $data;
    public $left;
    public $right;
    public  function __construct($data)
    {
        // Set node value
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class BinaryTree
{
    public $root;
    public  function __construct()
    {
        $this->root = NULL;
    }
    public  function levelNodes(&$record, $track, $level)
    {
        if ($track != NULL)
        {
            if (!array_key_exists($level, $record))
            {
                $record[$level] = array();
            }
            
            $record[$level][] = $track->data;
           
            // Visit left subtree
            $this->levelNodes($record, $track->left, $level + 1);
            // Visit right subtree
            $this->levelNodes($record, $track->right, $level + 1);
        }
    }
    // Display sorted nodes by level
    public  function showSortedNode()
    {
        if ($this->root == NULL)
        {
            return;
        }
        $record = array();
        $this->levelNodes($record, $this->root, 1);
        // Get number of level
        $n = count($record);
        for ($i = 1; $i <= $n; ++$i)
        {
            sort($record[$i]);
            // Print level nodes
            foreach($record[$i] as $key => $value)
            {
                echo("  ".$value);
            }
            echo("\n");
        }
    }
}

function main()
{
    $tree = new BinaryTree();
    /*
        Binary Tree
    -----------------------
             10
           /    \
          11     5
         / \    /  \
        1   3  7    2
           / \  \    \
          9  -1  8    4
    ----------------------           
    */
    $tree->root = new TreeNode(10);
    $tree->root->left = new TreeNode(11);
    $tree->root->right = new TreeNode(5);
    $tree->root->right->right = new TreeNode(2);
    $tree->root->right->right->right = new TreeNode(4);
    $tree->root->right->left = new TreeNode(7);
    $tree->root->right->left->right = new TreeNode(8);
    $tree->root->left->left = new TreeNode(1);
    $tree->root->left->right = new TreeNode(3);
    $tree->root->left->right->left = new TreeNode(9);
    $tree->root->left->right->right = new TreeNode(-1);
    $tree->showSortedNode();
}
main();

Output

  10
  5  11
  1  2  3  7
  -1  4  8  9
// Node JS Program
// Print binary tree levels in ascending order

// Binary Tree node
class TreeNode
{
    constructor(data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinaryTree
{
    constructor()
    {
        this.root = null;
    }
    levelNodes(record, track, level)
    {
        if (track != null)
        {
            if (!record.has(level))
            {
                record.set(level, []);
            }
            record.get(level).push(track.data);
            // Visit left subtree
            this.levelNodes(record, track.left, level + 1);
            // Visit right subtree
            this.levelNodes(record, track.right, level + 1);
        }
    }
    // Display sorted nodes by level
    showSortedNode()
    {
        if (this.root == null)
        {
            return;
        }
        var record = new Map();
        this.levelNodes(record, this.root, 1);
        // Get number of level
        var n = record.size;
        for (var i = 1; i <= n; ++i)
        {
            // Sort level nodes
            record.get(i).sort(function(a, b)
            {
                return a - b;
            });
            // Print level nodes
            record.get(i).forEach(function(value)
            {
                process.stdout.write(" " + value)
            })
            process.stdout.write("\n");
        }
    }
}

function main()
{
    var tree = new BinaryTree();
    /*
        Binary Tree
    -----------------------
             10
           /    \
          11     5
         / \    /  \
        1   3  7    2
           / \  \    \
          9  -1  8    4
    ----------------------           
    */
    tree.root = new TreeNode(10);
    tree.root.left = new TreeNode(11);
    tree.root.right = new TreeNode(5);
    tree.root.right.right = new TreeNode(2);
    tree.root.right.right.right = new TreeNode(4);
    tree.root.right.left = new TreeNode(7);
    tree.root.right.left.right = new TreeNode(8);
    tree.root.left.left = new TreeNode(1);
    tree.root.left.right = new TreeNode(3);
    tree.root.left.right.left = new TreeNode(9);
    tree.root.left.right.right = new TreeNode(-1);
    tree.showSortedNode();
}
main();

Output

 10
 5 11
 1 2 3 7
 -1 4 8 9
#  Python 3 Program
#  Print binary tree levels in ascending order

#  Binary Tree node
class TreeNode :
    def __init__(self, data) :
        #  Set node value
        self.data = data
        self.left = None
        self.right = None
    

class BinaryTree :
    def __init__(self) :
        self.root = None
    
    def levelNodes(self, record, track, level) :
        if (track != None) :
            if (not(level in record.keys())) :
                record[level] = []
            
            record.get(level).append(track.data)
            #  Visit left subtree
            self.levelNodes(record, track.left, level + 1)
            #  Visit right subtree
            self.levelNodes(record, track.right, level + 1)
        
    
    #  Display sorted nodes by level
    def showSortedNode(self) :
        if (self.root == None) :
            return
        
        record = dict()
        self.levelNodes(record, self.root, 1)
        #  Get number of level
        n = len(record)
        i = 1
        while (i <= n) :
            # sort level node
            record.get(i).sort()
            for v in record.get(i):
                print("  ", v, end = "")
            
            print(end = "\n")
            i += 1
        
    

def main() :
    tree = BinaryTree()
    #    Binary Tree
    # -----------------------
    #         10
    #       /    \
    #      11     5
    #     / \    /  \
    #    1   3  7    2
    #       / \  \    \
    #      9  -1  8    4
    # ----------------------           
    tree.root = TreeNode(10)
    tree.root.left = TreeNode(11)
    tree.root.right = TreeNode(5)
    tree.root.right.right = TreeNode(2)
    tree.root.right.right.right = TreeNode(4)
    tree.root.right.left = TreeNode(7)
    tree.root.right.left.right = TreeNode(8)
    tree.root.left.left = TreeNode(1)
    tree.root.left.right = TreeNode(3)
    tree.root.left.right.left = TreeNode(9)
    tree.root.left.right.right = TreeNode(-1)
    tree.showSortedNode()

if __name__ == "__main__": main()

Output

   10
   5   11
   1   2   3   7
   -1   4   8   9
require 'set'
#  Ruby Program
#  Print binary tree levels in ascending order

#  Binary Tree node
class TreeNode 
    # Define the accessor and reader of class TreeNode
    attr_reader :data, :left, :right
    attr_accessor :data, :left, :right
    def initialize(data) 
        #  Set node value
        self.data = data
        self.left = nil
        self.right = nil
    end

end

class BinaryTree 
    # Define the accessor and reader of class BinaryTree
    attr_reader :root
    attr_accessor :root
    def initialize() 
        self.root = nil
    end

    def levelNodes(record, track, level) 
        if (track != nil) 
            if (!record.key?(level)) 
                record[level] = SortedSet.new()
            end

            record[level].add(track.data)
            #  Visit left subtree
            self.levelNodes(record, track.left, level + 1)
            #  Visit right subtree
            self.levelNodes(record, track.right, level + 1)
        end

    end

    #  Display sorted nodes by level
    def showSortedNode() 
        if (self.root == nil) 
            return
        end

        record = Hash.new()
        self.levelNodes(record, self.root, 1)
        #  Get number of level
        n = record.size()
        i = 1
        while (i <= n) 
            #  Print level nodes
            record[i].each do |num|
                print(" ", num)
            end

            print("\n")
            i += 1
        end

    end

end

def main() 
    tree = BinaryTree.new()
    #    Binary Tree
    # -----------------------
    #         10
    #       /    \
    #      11     5
    #     / \    /  \
    #    1   3  7    2
    #       / \  \    \
    #      9  -1  8    4
    # ----------------------           
    tree.root = TreeNode.new(10)
    tree.root.left = TreeNode.new(11)
    tree.root.right = TreeNode.new(5)
    tree.root.right.right = TreeNode.new(2)
    tree.root.right.right.right = TreeNode.new(4)
    tree.root.right.left = TreeNode.new(7)
    tree.root.right.left.right = TreeNode.new(8)
    tree.root.left.left = TreeNode.new(1)
    tree.root.left.right = TreeNode.new(3)
    tree.root.left.right.left = TreeNode.new(9)
    tree.root.left.right.right = TreeNode.new(-1)
    tree.showSortedNode()
end

main()

Output

 10
 5 11
 1 2 3 7
 -1 4 8 9

import scala.collection.mutable._;
// Scala Program
// Print binary tree levels in ascending order

// Binary Tree node
class TreeNode(var data: Int,
    var left: TreeNode,
        var right: TreeNode)
{
    def this(data: Int)
    {
        // Set node value
        this(data, null, null);
    }
}
class BinaryTree(var root: TreeNode)
{
    def this()
    {
        this(null);
    }
    def levelNodes(record: HashMap[Int, HashSet[Int]], 
      track: TreeNode, level: Int): Unit = {
        if (track != null)
        {
            if (!record.contains(level))
            {
                record += (level -> new HashSet[Int]());
            }
            record.get(level).get.add(track.data);
            // Visit left subtree
            levelNodes(record, track.left, level + 1);
            // Visit right subtree
            levelNodes(record, track.right, level + 1);
        }
    }
    // Display sorted nodes by level
    def showSortedNode(): Unit = {
        if (this.root == null)
        {
            return;
        }
        var record = new HashMap[Int,HashSet[Int]]();
        this.levelNodes(record, this.root, 1);
        // Get number of level
        var n: Int = record.size;
        var i: Int = 1;
        while (i <= n)
        {
            // Print level nodes
            for (v <- record.get(i).get)
            {
                print("  " + v);
            }
            print("\n");
            i += 1;
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var tree: BinaryTree = new BinaryTree();
        /*
            Binary Tree
        -----------------------
                 10
               /    \
              11     5
             / \    /  \
            1   3  7    2
               / \  \    \
              9  -1  8    4
        ----------------------           
        */
        tree.root = new TreeNode(10);
        tree.root.left = new TreeNode(11);
        tree.root.right = new TreeNode(5);
        tree.root.right.right = new TreeNode(2);
        tree.root.right.right.right = new TreeNode(4);
        tree.root.right.left = new TreeNode(7);
        tree.root.right.left.right = new TreeNode(8);
        tree.root.left.left = new TreeNode(1);
        tree.root.left.right = new TreeNode(3);
        tree.root.left.right.left = new TreeNode(9);
        tree.root.left.right.right = new TreeNode(-1);
        tree.showSortedNode();
    }
}

Output

  10
  5  11
  1  2  3  7
  -1  4  8  9
import Foundation;
// Swift 4 Program
// Print binary tree levels in ascending order

// Binary Tree node
class TreeNode
{
    var data: Int;
    var left: TreeNode? ;
    var right: TreeNode? ;
    init(_ data: Int)
    {
        // Set node value
        self.data = data;
        self.left = nil;
        self.right = nil;
    }
}
class BinaryTree
{
    var root: TreeNode? ;
    init()
    {
        self.root = nil;
    }
    func levelNodes(_ record: inout[Int : Set<Int> ], 
      _ track: TreeNode? , _ level : Int)
    {
        if (track  != nil)
        {
            if (!record.keys.contains(level))
            {
                record[level] = Set<Int>();
            }
            record[level]!.insert(track!.data);
            // Visit left subtree
            self.levelNodes(&record, track!.left, level + 1);
            // Visit right subtree
            self.levelNodes(&record, track!.right, level + 1);
        }
    }
    // Display sorted nodes by level
    func showSortedNode()
    {
        if (self.root == nil)
        {
            return;
        }
        var record = [Int : Set<Int> ]();
        self.levelNodes(&record, self.root, 1);
        // Get number of level
        let n: Int = record.count;
        var i: Int = 1;
        while (i <= n)
        {
            // Print level nodes
            for v in record[i]!.sorted()
            {
                print("  ", v, terminator: "");
            }
            print(terminator: "\n");
            i += 1;
        }
    }
}
func main()
{
    let tree: BinaryTree = BinaryTree();
    /*
        Binary Tree
    -----------------------
             10
           /    \
          11     5
         / \    /  \
        1   3  7    2
           / \  \    \
          9  -1  8    4
    ----------------------           
    */
    tree.root = TreeNode(10);
    tree.root!.left = TreeNode(11);
    tree.root!.right = TreeNode(5);
    tree.root!.right!.right = TreeNode(2);
    tree.root!.right!.right!.right = TreeNode(4);
    tree.root!.right!.left = TreeNode(7);
    tree.root!.right!.left!.right = TreeNode(8);
    tree.root!.left!.left = TreeNode(1);
    tree.root!.left!.right = TreeNode(3);
    tree.root!.left!.right!.left = TreeNode(9);
    tree.root!.left!.right!.right = TreeNode(-1);
    tree.showSortedNode();
}
main();

Output

   10
   5   11
   1   2   3   7
   -1   4   8   9
// Kotlin Program
// Print binary tree levels in ascending order

// Binary Tree node
class TreeNode
{
    var data: Int;
    var left: TreeNode ? ;
    var right: TreeNode ? ;
    constructor(data: Int)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinaryTree
{
    var root: TreeNode ? ;
    constructor()
    {
        this.root = null;
    }
    fun levelNodes(record: HashMap < Int, HashSet < Int >> , 
                   track: TreeNode ? , level : Int): Unit
    {
        if (track != null)
        {
            if (!record.containsKey(level))
            {
                record.put(level,  hashSetOf <Int> ());
            }
            record.getValue(level).add(track.data);
            // Visit left subtree
            this.levelNodes(record, track.left, level + 1);
            // Visit right subtree
            this.levelNodes(record, track.right, level + 1);
        }
    }
    // Display sorted nodes by level
    fun showSortedNode(): Unit
    {
        if (this.root == null)
        {
            return;
        }
        val record = hashMapOf < Int, HashSet < Int >> ();
        this.levelNodes(record, this.root, 1);
        // Get number of level
        val n: Int = record.count();
        var i: Int = 1;
        while (i <= n)
        {
            // Print level nodes
            for (v in record.getValue(i))
            {
                print("  " + v);
            }
            print("\n");
            i += 1;
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val tree: BinaryTree = BinaryTree();
    /*
        Binary Tree
    -----------------------
             10
           /    \
          11     5
         / \    /  \
        1   3  7    2
           / \  \    \
          9  -1  8    4
    ----------------------           
    */
    tree.root = TreeNode(10);
    tree.root?.left = TreeNode(11);
    tree.root?.right = TreeNode(5);
    tree.root?.right?.right = TreeNode(2);
    tree.root?.right?.right?.right = TreeNode(4);
    tree.root?.right?.left = TreeNode(7);
    tree.root?.right?.left?.right = TreeNode(8);
    tree.root?.left?.left = TreeNode(1);
    tree.root?.left?.right = TreeNode(3);
    tree.root?.left?.right?.left = TreeNode(9);
    tree.root?.left?.right?.right = TreeNode(-1);
    tree.showSortedNode();
}

Output

  10
  5  11
  1  2  3  7
  -1  4  8  9

For practice task, solve this similar problem when level node is similar (duplicates).

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment