Count the number of visible nodes in Binary Tree
Here given code implementation process.
/*
C Program
Count the number of visible nodes in Binary Tree
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
//Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
//This is creating a binary tree node and return this
struct Node *get_node(int data)
{
// Create dynamic node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return new_node;
}
//Display pre order elements
void preorder(struct Node *node)
{
if (node != NULL)
{
//Print node value
printf(" %d", node->data);
preorder(node->left);
preorder(node->right);
}
}
//Count visible nodes
void count_visible_nodes(struct Node *node, int sum, int *counter)
{
if (node == NULL)
{
return;
}
int new_sum = 0;
if (node->data >= sum)
{
// When get a new big node in current path
*counter = *counter + 1;
// get new big node
new_sum = node->data;
}
else
{
new_sum = sum;
}
// Recursively visit left and right subtree
count_visible_nodes(node->left, new_sum, counter);
count_visible_nodes(node->right, new_sum, counter);
}
//Handles the request to find visible nodes
void visible_nodes(struct Node *root)
{
if (root == NULL)
{
printf("\n Empty Tree \n");
}
else
{
//Display tree elements
printf("\n Tree Nodes \n");
preorder(root);
int counter = 0;
count_visible_nodes(root, INT_MIN, & counter);
// Display calculated result
printf("\n Output : %d \n", counter);
}
}
int main()
{
struct Node *root = NULL;
/*
constructor binary tree
-----------------
8
/ \
5 18
/ \ \
1 3 2
/ \ \
19 9 21
/ \
12 4
-----------------
*/
root = get_node(8);
root->left = get_node(5);
root->left->right = get_node(3);
root->left->right->left = get_node(19);
root->left->right->right = get_node(9);
root->left->right->right->left = get_node(12);
root->left->right->right->right = get_node(4);
root->left->left = get_node(1);
root->right = get_node(18);
root->right->right = get_node(2);
root->right->right->right = get_node(21);
/*
Counter = 0
Paths
{} = empty
8 => new big in this path [Counter = 1]
8->5 => new node 5 is not big in this path
8->5->1 => new node 1 is not big in this path
8->5->3 => new node 3 is not big in this path
8->5->3->19 => 19 is new big in this path [Counter = 2]
8->5->3->9 => 9 is new big in this path [Counter = 3]
8->5->3->9->12 => 12 New Big in path Counter = 4
8->5->3->9->4 => new node 4 is not big in this path
8->10 = 10 is new big in this path [Counter = 5]
8->10->2 = new node 1 is not big in this path
8->10->2->21 = 21 is new big in this path [Counter = 6]
Result = 6
*/
visible_nodes(root);
return 0;
}
Output
Tree Nodes
8 5 1 3 19 9 12 4 18 2 21
Output : 6
/*
Java Program
Count the number of visible nodes in Binary Tree
*/
// Binary Tree node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public Node root;
public int counter;
public BinaryTree()
{
//Set initial tree root to null
this.root = null;
this.counter = 0;
}
//Display pre order elements
public void preorder(Node node)
{
if (node != null)
{
//Print node value
System.out.print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
//Count visible nodes
public void count_visible_nodes(Node node, int sum)
{
if (node == null)
{
return;
}
int new_sum = 0;
if (node.data >= sum)
{
// When get a new big node in current path
this.counter = this.counter + 1;
// get new big node
new_sum = node.data;
}
else
{
new_sum = sum;
}
// Recursively visit left and right subtree
count_visible_nodes(node.left, new_sum);
count_visible_nodes(node.right, new_sum);
}
//Handles the request to find visible nodes
public void visible_nodes()
{
if (this.root == null)
{
System.out.print("\n Empty Tree \n");
}
else
{
//Display tree elements
System.out.print("\n Tree Nodes \n");
preorder(this.root);
this.counter = 0;
count_visible_nodes(this.root, Integer.MIN_VALUE);
// Display calculated result
System.out.print("\n Output : " + this.counter + " \n");
}
}
public static void main(String[] args)
{
//Create tree object
BinaryTree tree = new BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
5 18
/ \ \
1 3 2
/ \ \
19 9 21
/ \
12 4
-----------------
*/
tree.root = new Node(8);
tree.root.left = new Node(5);
tree.root.left.right = new Node(3);
tree.root.left.right.left = new Node(19);
tree.root.left.right.right = new Node(9);
tree.root.left.right.right.left = new Node(12);
tree.root.left.right.right.right = new Node(4);
tree.root.left.left = new Node(1);
tree.root.right = new Node(18);
tree.root.right.right = new Node(2);
tree.root.right.right.right = new Node(21);
/*
Counter = 0
Paths
{} = empty
8 => new big in this path [Counter = 1]
8->5 => new node 5 is not big in this path
8->5->1 => new node 1 is not big in this path
8->5->3 => new node 3 is not big in this path
8->5->3->19 => 19 is new big in this path [Counter = 2]
8->5->3->9 => 9 is new big in this path [Counter = 3]
8->5->3->9->12 => 12 New Big in path Counter = 4
8->5->3->9->4 => new node 4 is not big in this path
8->10 = 10 is new big in this path [Counter = 5]
8->10->2 = new node 1 is not big in this path
8->10->2->21 = 21 is new big in this path [Counter = 6]
Result = 6
*/
tree.visible_nodes();
}
}
Output
Tree Nodes
8 5 1 3 19 9 12 4 18 2 21
Output : 6
// Include header file
#include <iostream>
#include<limits.h>
using namespace std;
/*
C++ Program
Count the number of visible nodes in Binary Tree
*/
// Binary Tree node
class Node
{
public: int data;
Node *left;
Node *right;
Node(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: Node *root;
int counter;
BinaryTree()
{
// Set initial tree root to null
this->root = NULL;
this->counter = 0;
}
// Display pre order elements
void preorder(Node *node)
{
if (node != NULL)
{
// Print node value
cout << " " << node->data;
this->preorder(node->left);
this->preorder(node->right);
}
}
// Count visible nodes
void count_visible_nodes(Node *node, int sum)
{
if (node == NULL)
{
return;
}
int new_sum = 0;
if (node->data >= sum)
{
// When get a new big node in current path
this->counter = this->counter + 1;
// get new big node
new_sum = node->data;
}
else
{
new_sum = sum;
}
// Recursively visit left and right subtree
this->count_visible_nodes(node->left, new_sum);
this->count_visible_nodes(node->right, new_sum);
}
// Handles the request to find visible nodes
void visible_nodes()
{
if (this->root == NULL)
{
cout << "\n Empty Tree \n";
}
else
{
// Display tree elements
cout << "\n Tree Nodes \n";
this->preorder(this->root);
this->counter = 0;
this->count_visible_nodes(this->root, INT_MIN);
// Display calculated result
cout << "\n Output : " << this->counter << " \n";
}
}
};
int main()
{
// Create tree object
BinaryTree tree = BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
5 18
/ \ \
1 3 2
/ \ \
19 9 21
/ \
12 4
-----------------
*/
tree.root = new Node(8);
tree.root->left = new Node(5);
tree.root->left->right = new Node(3);
tree.root->left->right->left = new Node(19);
tree.root->left->right->right = new Node(9);
tree.root->left->right->right->left = new Node(12);
tree.root->left->right->right->right = new Node(4);
tree.root->left->left = new Node(1);
tree.root->right = new Node(18);
tree.root->right->right = new Node(2);
tree.root->right->right->right = new Node(21);
/*
Counter = 0
Paths
{} = empty
8 => new big in this path [Counter = 1]
8->5 => new node 5 is not big in this path
8->5->1 => new node 1 is not big in this path
8->5->3 => new node 3 is not big in this path
8->5->3->19 => 19 is new big in this path [Counter = 2]
8->5->3->9 => 9 is new big in this path [Counter = 3]
8->5->3->9->12 => 12 New Big in path Counter = 4
8->5->3->9->4 => new node 4 is not big in this path
8->10 = 10 is new big in this path [Counter = 5]
8->10->2 = new node 1 is not big in this path
8->10->2->21 = 21 is new big in this path [Counter = 6]
Result = 6
*/
tree.visible_nodes();
return 0;
}
Output
Tree Nodes
8 5 1 3 19 9 12 4 18 2 21
Output : 6
// Include namespace system
using System;
/*
C# Program
Count the number of visible nodes in Binary Tree
*/
// Binary Tree node
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public Node root;
public int counter;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
this.counter = 0;
}
// Display pre order elements
public void preorder(Node node)
{
if (node != null)
{
// Print node value
Console.Write(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// Count visible nodes
public void count_visible_nodes(Node node, int sum)
{
if (node == null)
{
return;
}
int new_sum = 0;
if (node.data >= sum)
{
// When get a new big node in current path
this.counter = this.counter + 1;
// get new big node
new_sum = node.data;
}
else
{
new_sum = sum;
}
// Recursively visit left and right subtree
count_visible_nodes(node.left, new_sum);
count_visible_nodes(node.right, new_sum);
}
// Handles the request to find visible nodes
public void visible_nodes()
{
if (this.root == null)
{
Console.Write("\n Empty Tree \n");
}
else
{
// Display tree elements
Console.Write("\n Tree Nodes \n");
preorder(this.root);
this.counter = 0;
count_visible_nodes(this.root, int.MinValue);
// Display calculated result
Console.Write("\n Output : " + this.counter + " \n");
}
}
public static void Main(String[] args)
{
// Create tree object
BinaryTree tree = new BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
5 18
/ \ \
1 3 2
/ \ \
19 9 21
/ \
12 4
-----------------
*/
tree.root = new Node(8);
tree.root.left = new Node(5);
tree.root.left.right = new Node(3);
tree.root.left.right.left = new Node(19);
tree.root.left.right.right = new Node(9);
tree.root.left.right.right.left = new Node(12);
tree.root.left.right.right.right = new Node(4);
tree.root.left.left = new Node(1);
tree.root.right = new Node(18);
tree.root.right.right = new Node(2);
tree.root.right.right.right = new Node(21);
/*
Counter = 0
Paths
{} = empty
8 => new big in this path [Counter = 1]
8->5 => new node 5 is not big in this path
8->5->1 => new node 1 is not big in this path
8->5->3 => new node 3 is not big in this path
8->5->3->19 => 19 is new big in this path [Counter = 2]
8->5->3->9 => 9 is new big in this path [Counter = 3]
8->5->3->9->12 => 12 New Big in path Counter = 4
8->5->3->9->4 => new node 4 is not big in this path
8->10 = 10 is new big in this path [Counter = 5]
8->10->2 = new node 1 is not big in this path
8->10->2->21 = 21 is new big in this path [Counter = 6]
Result = 6
*/
tree.visible_nodes();
}
}
Output
Tree Nodes
8 5 1 3 19 9 12 4 18 2 21
Output : 6
<?php
/*
Php Program
Count the number of visible nodes in Binary Tree
*/
// Binary Tree node
class Node
{
public $data;
public $left;
public $right;
function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class BinaryTree
{
public $root;
public $counter;
function __construct()
{
// Set initial tree root to null
$this->root = null;
$this->counter = 0;
}
// Display pre order elements
public function preorder($node)
{
if ($node != null)
{
// Print node value
echo " ". $node->data;
$this->preorder($node->left);
$this->preorder($node->right);
}
}
// Count visible nodes
public function count_visible_nodes($node, $sum)
{
if ($node == null)
{
return;
}
$new_sum = 0;
if ($node->data >= $sum)
{
// When get a new big node in current path
$this->counter = $this->counter + 1;
// get new big node
$new_sum = $node->data;
}
else
{
$new_sum = $sum;
}
// Recursively visit left and right subtree
$this->count_visible_nodes($node->left, $new_sum);
$this->count_visible_nodes($node->right, $new_sum);
}
// Handles the request to find visible nodes
public function visible_nodes()
{
if ($this->root == null)
{
echo "\n Empty Tree \n";
}
else
{
// Display tree elements
echo "\n Tree Nodes \n";
$this->preorder($this->root);
$this->counter = 0;
$this->count_visible_nodes($this->root, -PHP_INT_MAX);
// Display calculated result
echo "\n Output : ". $this->counter ." \n";
}
}
}
function main()
{
// Create tree object
$tree = new BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
5 18
/ \ \
1 3 2
/ \ \
19 9 21
/ \
12 4
-----------------
*/
$tree->root = new Node(8);
$tree->root->left = new Node(5);
$tree->root->left->right = new Node(3);
$tree->root->left->right->left = new Node(19);
$tree->root->left->right->right = new Node(9);
$tree->root->left->right->right->left = new Node(12);
$tree->root->left->right->right->right = new Node(4);
$tree->root->left->left = new Node(1);
$tree->root->right = new Node(18);
$tree->root->right->right = new Node(2);
$tree->root->right->right->right = new Node(21);
/*
Counter = 0
Paths
{} = empty
8 => new big in this path [Counter = 1]
8->5 => new node 5 is not big in this path
8->5->1 => new node 1 is not big in this path
8->5->3 => new node 3 is not big in this path
8->5->3->19 => 19 is new big in this path [Counter = 2]
8->5->3->9 => 9 is new big in this path [Counter = 3]
8->5->3->9->12 => 12 New Big in path Counter = 4
8->5->3->9->4 => new node 4 is not big in this path
8->10 = 10 is new big in this path [Counter = 5]
8->10->2 = new node 1 is not big in this path
8->10->2->21 = 21 is new big in this path [Counter = 6]
Result = 6
*/
$tree->visible_nodes();
}
main();
Output
Tree Nodes
8 5 1 3 19 9 12 4 18 2 21
Output : 6
/*
Node Js Program
Count the number of visible nodes in Binary Tree
*/
// Binary Tree node
class Node
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
// Set initial tree root to null
this.root = null;
this.counter = 0;
}
// Display pre order elements
preorder(node)
{
if (node != null)
{
// Print node value
process.stdout.write(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
// Count visible nodes
count_visible_nodes(node, sum)
{
if (node == null)
{
return;
}
var new_sum = 0;
if (node.data >= sum)
{
// When get a new big node in current path
this.counter = this.counter + 1;
// get new big node
new_sum = node.data;
}
else
{
new_sum = sum;
}
// Recursively visit left and right subtree
this.count_visible_nodes(node.left, new_sum);
this.count_visible_nodes(node.right, new_sum);
}
// Handles the request to find visible nodes
visible_nodes()
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree \n");
}
else
{
// Display tree elements
process.stdout.write("\n Tree Nodes \n");
this.preorder(this.root);
this.counter = 0;
this.count_visible_nodes(this.root, -Number.MAX_VALUE);
// Display calculated result
process.stdout.write("\n Output : " + this.counter + " \n");
}
}
}
function main()
{
// Create tree object
var tree = new BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
5 18
/ \ \
1 3 2
/ \ \
19 9 21
/ \
12 4
-----------------
*/
tree.root = new Node(8);
tree.root.left = new Node(5);
tree.root.left.right = new Node(3);
tree.root.left.right.left = new Node(19);
tree.root.left.right.right = new Node(9);
tree.root.left.right.right.left = new Node(12);
tree.root.left.right.right.right = new Node(4);
tree.root.left.left = new Node(1);
tree.root.right = new Node(18);
tree.root.right.right = new Node(2);
tree.root.right.right.right = new Node(21);
/*
Counter = 0
Paths
{} = empty
8 => new big in this path [Counter = 1]
8->5 => new node 5 is not big in this path
8->5->1 => new node 1 is not big in this path
8->5->3 => new node 3 is not big in this path
8->5->3->19 => 19 is new big in this path [Counter = 2]
8->5->3->9 => 9 is new big in this path [Counter = 3]
8->5->3->9->12 => 12 New Big in path Counter = 4
8->5->3->9->4 => new node 4 is not big in this path
8->10 = 10 is new big in this path [Counter = 5]
8->10->2 = new node 1 is not big in this path
8->10->2->21 = 21 is new big in this path [Counter = 6]
Result = 6
*/
tree.visible_nodes();
}
main();
Output
Tree Nodes
8 5 1 3 19 9 12 4 18 2 21
Output : 6
import sys
# Python 3 Program
# Count the number of visible nodes in Binary Tree
# Binary Tree node
class Node :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
# Set initial tree root to null
self.root = None
self.counter = 0
# Display pre order elements
def preorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.preorder(node.left)
self.preorder(node.right)
# Count visible nodes
def count_visible_nodes(self, node, sum) :
if (node == None) :
return
new_sum = 0
if (node.data >= sum) :
# When get a new big node in current path
self.counter = self.counter + 1
# get new big node
new_sum = node.data
else :
new_sum = sum
# Recursively visit left and right subtree
self.count_visible_nodes(node.left, new_sum)
self.count_visible_nodes(node.right, new_sum)
# Handles the request to find visible nodes
def visible_nodes(self) :
if (self.root == None) :
print("\n Empty Tree \n", end = "")
else :
# Display tree elements
print("\n Tree Nodes \n", end = "")
self.preorder(self.root)
self.counter = 0
self.count_visible_nodes(self.root, -sys.maxsize)
# Display calculated result
print("\n Output : ", self.counter ," \n", end = "")
def main() :
# Create tree object
tree = BinaryTree()
#
# constructor binary tree
# -----------------
# 8
# / \
# 5 18
# / \ \
# 1 3 2
# / \ \
# 19 9 21
# / \
# 12 4
# -----------------
#
tree.root = Node(8)
tree.root.left = Node(5)
tree.root.left.right = Node(3)
tree.root.left.right.left = Node(19)
tree.root.left.right.right = Node(9)
tree.root.left.right.right.left = Node(12)
tree.root.left.right.right.right = Node(4)
tree.root.left.left = Node(1)
tree.root.right = Node(18)
tree.root.right.right = Node(2)
tree.root.right.right.right = Node(21)
#
# Counter = 0
# Paths
# {} = empty
# 8 => new big in this path [Counter = 1]
# 8->5 => new node 5 is not big in this path
# 8->5->1 => new node 1 is not big in this path
# 8->5->3 => new node 3 is not big in this path
# 8->5->3->19 => 19 is new big in this path [Counter = 2]
# 8->5->3->9 => 9 is new big in this path [Counter = 3]
# 8->5->3->9->12 => 12 New Big in path Counter = 4
# 8->5->3->9->4 => new node 4 is not big in this path
# 8->10 = 10 is new big in this path [Counter = 5]
# 8->10->2 = new node 1 is not big in this path
# 8->10->2->21 = 21 is new big in this path [Counter = 6]
# Result = 6
#
tree.visible_nodes()
if __name__ == "__main__": main()
Output
Tree Nodes
8 5 1 3 19 9 12 4 18 2 21
Output : 6
# Ruby Program
# Count the number of visible nodes in Binary Tree
# Binary Tree node
class Node
# Define the accessor and reader of class Node
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, :counter
attr_accessor :root, :counter
def initialize()
# Set initial tree root to null
self.root = nil
self.counter = 0
end
# Display pre order elements
def preorder(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.preorder(node.left)
self.preorder(node.right)
end
end
# Count visible nodes
def count_visible_nodes(node, sum)
if (node == nil)
return
end
new_sum = 0
if (node.data >= sum)
# When get a new big node in current path
self.counter = self.counter + 1
# get new big node
new_sum = node.data
else
new_sum = sum
end
# Recursively visit left and right subtree
self.count_visible_nodes(node.left, new_sum)
self.count_visible_nodes(node.right, new_sum)
end
# Handles the request to find visible nodes
def visible_nodes()
if (self.root == nil)
print("\n Empty Tree \n")
else
# Display tree elements
print("\n Tree Nodes \n")
self.preorder(self.root)
self.counter = 0
self.count_visible_nodes(self.root, -(2 ** (0. size * 8 - 2)))
# Display calculated result
print("\n Output : ", self.counter ," \n")
end
end
end
def main()
# Create tree object
tree = BinaryTree.new()
#
# constructor binary tree
# -----------------
# 8
# / \
# 5 18
# / \ \
# 1 3 2
# / \ \
# 19 9 21
# / \
# 12 4
# -----------------
#
tree.root = Node.new(8)
tree.root.left = Node.new(5)
tree.root.left.right = Node.new(3)
tree.root.left.right.left = Node.new(19)
tree.root.left.right.right = Node.new(9)
tree.root.left.right.right.left = Node.new(12)
tree.root.left.right.right.right = Node.new(4)
tree.root.left.left = Node.new(1)
tree.root.right = Node.new(18)
tree.root.right.right = Node.new(2)
tree.root.right.right.right = Node.new(21)
#
# Counter = 0
# Paths
# {} => empty
# 8 => new big in this path [Counter = 1]
# 8->5 => new node 5 is not big in this path
# 8->5->1 => new node 1 is not big in this path
# 8->5->3 => new node 3 is not big in this path
# 8->5->3->19 => 19 is new big in this path [Counter = 2]
# 8->5->3->9 => 9 is new big in this path [Counter = 3]
# 8->5->3->9->12 => 12 New Big in path Counter = 4
# 8->5->3->9->4 => new node 4 is not big in this path
# 8->10 = 10 is new big in this path [Counter = 5]
# 8->10->2 = new node 1 is not big in this path
# 8->10->2->21 = 21 is new big in this path [Counter = 6]
# Result = 6
#
tree.visible_nodes()
end
main()
Output
Tree Nodes
8 5 1 3 19 9 12 4 18 2 21
Output : 6
/*
Scala Program
Count the number of visible nodes in Binary Tree
*/
// Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: Node , var counter: Int)
{
def this()
{
this(null, 0);
}
// Display pre order elements
def preorder(node: Node): Unit = {
if (node != null)
{
// Print node value
print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// Count visible nodes
def count_visible_nodes(node: Node, sum: Int): Unit = {
if (node == null)
{
return;
}
var new_sum: Int = 0;
if (node.data >= sum)
{
// When get a new big node in current path
this.counter = this.counter + 1;
// get new big node
new_sum = node.data;
}
else
{
new_sum = sum;
}
// Recursively visit left and right subtree
count_visible_nodes(node.left, new_sum);
count_visible_nodes(node.right, new_sum);
}
// Handles the request to find visible nodes
def visible_nodes(): Unit = {
if (this.root == null)
{
print("\n Empty Tree \n");
}
else
{
// Display tree elements
print("\n Tree Nodes \n");
preorder(this.root);
this.counter = 0;
count_visible_nodes(this.root, Int.MinValue);
// Display calculated result
print("\n Output : " + this.counter + " \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create tree object
var tree: BinaryTree = new BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
5 18
/ \ \
1 3 2
/ \ \
19 9 21
/ \
12 4
-----------------
*/
tree.root = new Node(8);
tree.root.left = new Node(5);
tree.root.left.right = new Node(3);
tree.root.left.right.left = new Node(19);
tree.root.left.right.right = new Node(9);
tree.root.left.right.right.left = new Node(12);
tree.root.left.right.right.right = new Node(4);
tree.root.left.left = new Node(1);
tree.root.right = new Node(18);
tree.root.right.right = new Node(2);
tree.root.right.right.right = new Node(21);
/*
Counter = 0
Paths
{} = empty
8 => new big in this path [Counter = 1]
8->5 => new node 5 is not big in this path
8->5->1 => new node 1 is not big in this path
8->5->3 => new node 3 is not big in this path
8->5->3->19 => 19 is new big in this path [Counter = 2]
8->5->3->9 => 9 is new big in this path [Counter = 3]
8->5->3->9->12 => 12 New Big in path Counter = 4
8->5->3->9->4 => new node 4 is not big in this path
8->10 = 10 is new big in this path [Counter = 5]
8->10->2 = new node 1 is not big in this path
8->10->2->21 = 21 is new big in this path [Counter = 6]
Result = 6
*/
tree.visible_nodes();
}
}
Output
Tree Nodes
8 5 1 3 19 9 12 4 18 2 21
Output : 6
/*
Swift 4 Program
Count the number of visible nodes in Binary Tree
*/
// Binary Tree node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: Node? ;
var counter: Int;
init()
{
// Set initial tree root to null
self.root = nil;
self.counter = 0;
}
// Display pre order elements
func preorder(_ node: Node? )
{
if (node != nil)
{
// Print node value
print(" ", node!.data, terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
// Count visible nodes
func count_visible_nodes(_ node: Node? , _ sum : Int)
{
if (node == nil)
{
return;
}
var new_sum: Int = 0;
if (node!.data >= sum)
{
// When get a new big node in current path
self.counter = self.counter + 1;
// get new big node
new_sum = node!.data;
}
else
{
new_sum = sum;
}
// Recursively visit left and right subtree
self.count_visible_nodes(node!.left, new_sum);
self.count_visible_nodes(node!.right, new_sum);
}
// Handles the request to find visible nodes
func visible_nodes()
{
if (self.root == nil)
{
print("\n Empty Tree \n", terminator: "");
}
else
{
// Display tree elements
print("\n Tree Nodes \n", terminator: "");
self.preorder(self.root);
self.counter = 0;
self.count_visible_nodes(self.root, Int.min);
// Display calculated result
print("\n Output : ", self.counter ," \n", terminator: "");
}
}
}
func main()
{
// Create tree object
let tree: BinaryTree = BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
5 18
/ \ \
1 3 2
/ \ \
19 9 21
/ \
12 4
-----------------
*/
tree.root = Node(8);
tree.root!.left = Node(5);
tree.root!.left!.right = Node(3);
tree.root!.left!.right!.left = Node(19);
tree.root!.left!.right!.right = Node(9);
tree.root!.left!.right!.right!.left = Node(12);
tree.root!.left!.right!.right!.right = Node(4);
tree.root!.left!.left = Node(1);
tree.root!.right = Node(18);
tree.root!.right!.right = Node(2);
tree.root!.right!.right!.right = Node(21);
/*
Counter = 0
Paths
{} = empty
8 => new big in this path [Counter = 1]
8->5 => new node 5 is not big in this path
8->5->1 => new node 1 is not big in this path
8->5->3 => new node 3 is not big in this path
8->5->3->19 => 19 is new big in this path [Counter = 2]
8->5->3->9 => 9 is new big in this path [Counter = 3]
8->5->3->9->12 => 12 New Big in path Counter = 4
8->5->3->9->4 => new node 4 is not big in this path
8->10 = 10 is new big in this path [Counter = 5]
8->10->2 = new node 1 is not big in this path
8->10->2->21 = 21 is new big in this path [Counter = 6]
Result = 6
*/
tree.visible_nodes();
}
main();
Output
Tree Nodes
8 5 1 3 19 9 12 4 18 2 21
Output : 6
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