Skip to main content

Find number of node exist in Euler Tour of Binary Tree

Here given code implementation process.

/*
    C Program 
    Find number of node exist in Euler Tour of Binary Tree
*/
#include <stdio.h>
#include <stdlib.h>

// Tree Node
struct TreeNode
{
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

// Binary Tree
struct BinaryTree
{
    struct TreeNode *root;
};
// Create new tree
struct BinaryTree *new_tree()
{
    // Create dynamic node
    struct BinaryTree *tree = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
    if (tree != NULL)
    {
        tree->root = NULL;
    }
    else
    {
        printf("Memory Overflow to Create tree Tree\n");
    }
    //return new tree
    return tree;
}
// returns a new node of tree
struct TreeNode *new_node(int data)
{
    // Create dynamic node
    struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
    if (node != NULL)
    {
        //Set data and pointer values
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    }
    else
    {
        //This is indicates, segmentation fault or memory overflow problem
        printf("Memory Overflow\n");
    }
    //return new node
    return node;
}

// Count the number of nodes in euler path of given tree
int euler_path_node(struct TreeNode*node,struct TreeNode *parent)
{

    if(node==NULL)
    {
        // When tree node empty
        return 0;
    }
    //Recursively executing the left and right subtree and count nodes

    int count = euler_path_node(node->left, node) + euler_path_node(node->right, node) + 1;


    if(parent != NULL)
    {
        return count+1;
    }
    else
    {
        return count;
    }

   
}

// Handles the request of printing the euler path
void euler_path(struct TreeNode*root)
{

    if(root==NULL)
    {
        printf("\n Empty Tree \n");  
    }
    else
    {
       int ans = euler_path_node(root,NULL);

       printf(" Total Node is : %d\n",ans);
    }
}

int main()
{
    struct BinaryTree *tree = new_tree();

    /*
            9
           / \
          5   7
         / \   \
        1   6   11
       /   / \   \
      10  4   8   20
               \
                3
    -----------------------
        Binary Tree
    */

    tree->root = new_node(9);
    tree->root->left = new_node(5); 
    tree->root->right = new_node(7); 
    tree->root->left->left = new_node(1); 
    tree->root->left->left->left = new_node(10); 
    tree->root->left->right = new_node(6);
    tree->root->left->right->left = new_node(4);
    tree->root->left->right->right = new_node(8);
    tree->root->left->right->right->right = new_node(3);
    tree->root->right->right = new_node(11);
    tree->root->right->right->right = new_node(20);  

    // Euler path : 9 5 1 10 1 5 6 4 6 8 2 8 3 8 6 5 9 7 11 20 11 7 9
    // Output 23
    euler_path(tree->root);
    return 0;
}

Output

 Total Node is : 21
/*
    Java Program 
    Find number of node exist in Euler Tour of Binary Tree
*/
// Tree Node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Binary Tree
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		this.root = null;
	}
	// Count the number of nodes in euler path of given tree
	public int euler_path_node(TreeNode node, TreeNode parent)
	{
		if (node == null)
		{
			// When tree node empty
			return 0;
		}
		//Recursively executing the left and right subtree and count nodes
		int count = euler_path_node(node.left, node) + euler_path_node(node.right, node) + 1;
		if (parent != null)
		{
			return count + 1;
		}
		else
		{
			return count;
		}
	}
	// Handles the request of printing the euler path
	public void euler_path()
	{
		if (this.root == null)
		{
			System.out.print("\n Empty Tree \n");
		}
		else
		{
			int ans = euler_path_node(this.root, null);
			System.out.print(" Total Node is : " + ans + "\n");
		}
	}
	public static void main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		        9
		       / \
		      5   7
		     / \   \
		    1   6   11
		   /   / \   \
		  10  4   8   20
		           \
		            3
		-----------------------
		    Binary Tree
		*/
		tree.root = new TreeNode(9);
		tree.root.left = new TreeNode(5);
		tree.root.right = new TreeNode(7);
		tree.root.left.left = new TreeNode(1);
		tree.root.left.left.left = new TreeNode(10);
		tree.root.left.right = new TreeNode(6);
		tree.root.left.right.left = new TreeNode(4);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.right = new TreeNode(3);
		tree.root.right.right = new TreeNode(11);
		tree.root.right.right.right = new TreeNode(20);
		tree.euler_path();
	}
}

Output

 Total Node is : 21
// Include header file
#include <iostream>
using namespace std;

/*
    C++ Program 
    Find number of node exist in Euler Tour of Binary Tree
*/

//  Tree Node
class TreeNode
{
    public: 
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
//  Binary Tree
class BinaryTree
{
    public: 
    TreeNode *root;
    BinaryTree()
    {
        this->root = NULL;
    }
    //  Count the number of nodes in euler path of given tree
    int euler_path_node(TreeNode *node, TreeNode *parent)
    {
        if (node == NULL)
        {
            //  When tree node empty
            return 0;
        }
        // Recursively executing the left and right subtree and count nodes
        int count = this->euler_path_node(node->left, node) + this->euler_path_node(node->right, node) + 1;
        if (parent != NULL)
        {
            return count + 1;
        }
        else
        {
            return count;
        }
    }
    //  Handles the request of printing the euler path
    void euler_path()
    {
        if (this->root == NULL)
        {
            cout << "\n Empty Tree \n";
        }
        else
        {
            int ans = this->euler_path_node(this->root, NULL);
            cout << " Total Node is : " << ans << "\n";
        }
    }
};
int main()
{
    BinaryTree tree = BinaryTree();
    /*
            9
           / \
          5   7
         / \   \
        1   6   11
       /   / \   \
      10  4   8   20
               \
                3
    -----------------------
        Binary Tree
    */
    tree.root = new TreeNode(9);
    tree.root->left = new TreeNode(5);
    tree.root->right = new TreeNode(7);
    tree.root->left->left = new TreeNode(1);
    tree.root->left->left->left = new TreeNode(10);
    tree.root->left->right = new TreeNode(6);
    tree.root->left->right->left = new TreeNode(4);
    tree.root->left->right->right = new TreeNode(8);
    tree.root->left->right->right->right = new TreeNode(3);
    tree.root->right->right = new TreeNode(11);
    tree.root->right->right->right = new TreeNode(20);
    tree.euler_path();
    return 0;
}

Output

 Total Node is : 21
// Include namespace system
using System;
/*
    C# Program 
    Find number of node exist in Euler Tour of Binary Tree
*/
//  Tree Node
public class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
//  Binary Tree
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        this.root = null;
    }
    //  Count the number of nodes in euler path of given tree
    public int euler_path_node(TreeNode node, TreeNode parent)
    {
        if (node == null)
        {
            //  When tree node empty
            return 0;
        }
        // Recursively executing the left and right subtree and count nodes
        int count = euler_path_node(node.left, node) + euler_path_node(node.right, node) + 1;
        if (parent != null)
        {
            return count + 1;
        }
        else
        {
            return count;
        }
    }
    //  Handles the request of printing the euler path
    public void euler_path()
    {
        if (this.root == null)
        {
            Console.Write("\n Empty Tree \n");
        }
        else
        {
            int ans = euler_path_node(this.root, null);
            Console.Write(" Total Node is : " + ans + "\n");
        }
    }
    public static void Main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        /*
                9
               / \
              5   7
             / \   \
            1   6   11
           /   / \   \
          10  4   8   20
                   \
                    3
        -----------------------
            Binary Tree
        */
        tree.root = new TreeNode(9);
        tree.root.left = new TreeNode(5);
        tree.root.right = new TreeNode(7);
        tree.root.left.left = new TreeNode(1);
        tree.root.left.left.left = new TreeNode(10);
        tree.root.left.right = new TreeNode(6);
        tree.root.left.right.left = new TreeNode(4);
        tree.root.left.right.right = new TreeNode(8);
        tree.root.left.right.right.right = new TreeNode(3);
        tree.root.right.right = new TreeNode(11);
        tree.root.right.right.right = new TreeNode(20);
        tree.euler_path();
    }
}

Output

 Total Node is : 21
<?php
/*
    Php Program 
    Find number of node exist in Euler Tour of Binary Tree
*/
//  Tree Node
class TreeNode
{
    public $data;
    public $left;
    public $right;

    function __construct($data)
    {
        $this->data = $data;
        $this->left = null;
        $this->right = null;
    }
}
//  Binary Tree
class BinaryTree
{
    public $root;

    function __construct()
    {
        $this->root = null;
    }
    //  Count the number of nodes in euler path of given tree
    public  function euler_path_node($node, $parent)
    {
        if ($node == null)
        {
            //  When tree node empty
            return 0;
        }
        // Recursively executing the left and right subtree and count nodes
        $count = $this->euler_path_node($node->left, $node) + $this->euler_path_node($node->right, $node) + 1;
        if ($parent != null)
        {
            return $count + 1;
        }
        else
        {
            return $count;
        }
    }
    //  Handles the request of printing the euler path
    public  function euler_path()
    {
        if ($this->root == null)
        {
            echo "\n Empty Tree \n";
        }
        else
        {
            $ans = $this->euler_path_node($this->root, null);
            echo " Total Node is : ". $ans ."\n";
        }
    }
}

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

Output

 Total Node is : 21
/*
    Node Js Program 
    Find number of node exist in Euler Tour of Binary Tree
*/
//  Tree Node
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
//  Binary Tree
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	//  Count the number of nodes in euler path of given tree
	euler_path_node(node, parent)
	{
		if (node == null)
		{
			//  When tree node empty
			return 0;
		}
		// Recursively executing the left and right subtree and count nodes
		var count = this.euler_path_node(node.left, node) + this.euler_path_node(node.right, node) + 1;
		if (parent != null)
		{
			return count + 1;
		}
		else
		{
			return count;
		}
	}
	//  Handles the request of printing the euler path
	euler_path()
	{
		if (this.root == null)
		{
			process.stdout.write("\n Empty Tree \n");
		}
		else
		{
			var ans = this.euler_path_node(this.root, null);
			process.stdout.write(" Total Node is : " + ans + "\n");
		}
	}
}

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

Output

 Total Node is : 21
#  Python 3 Program 
#  Find number of node exist in Euler Tour of Binary Tree

#  Tree Node
class TreeNode :
	
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

#  Binary Tree
class BinaryTree :
	
	def __init__(self) :
		self.root = None
	
	#  Count the number of nodes in euler path of given tree
	def euler_path_node(self, node, parent) :
		if (node == None) :
			#  When tree node empty
			return 0
		
		# Recursively executing the left and right subtree and count nodes
		count = self.euler_path_node(node.left, node) + self.euler_path_node(node.right, node) + 1
		if (parent != None) :
			return count + 1
		else :
			return count
		
	
	#  Handles the request of printing the euler path
	def euler_path(self) :
		if (self.root == None) :
			print("\n Empty Tree \n", end = "")
		else :
			ans = self.euler_path_node(self.root, None)
			print(" Total Node is : ", ans ,"\n", end = "")
		
	

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

if __name__ == "__main__": main()

Output

 Total Node is :  21
#  Ruby Program 
#  Find number of node exist in Euler Tour of Binary Tree

#  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) 
		self.data = data
		self.left = nil
		self.right = nil
	end

end

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

	#  Count the number of nodes in euler path of given tree
	def euler_path_node(node, parent) 
		if (node == nil) 
			#  When tree node empty
			return 0
		end

		# Recursively executing the left and right subtree and count nodes
		count = self.euler_path_node(node.left, node) + self.euler_path_node(node.right, node) + 1
		if (parent != nil) 
			return count + 1
		else 
			return count
		end

	end

	#  Handles the request of printing the euler path
	def euler_path() 
		if (self.root == nil) 
			print("\n Empty Tree \n")
		else 
			ans = self.euler_path_node(self.root, nil)
			print(" Total Node is : ", ans ,"\n")
		end

	end

end

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

main()

Output

 Total Node is : 21
/*
    Scala Program 
    Find number of node exist in Euler Tour of Binary Tree
*/
//  Tree Node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
//  Binary Tree
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	//  Count the number of nodes in euler path of given tree
	def euler_path_node(node: TreeNode, parent: TreeNode): Int = {
		if (node == null)
		{
			//  When tree node empty
			return 0;
		}
		// Recursively executing the left and right subtree and count nodes
		var count: Int = euler_path_node(node.left, node) + euler_path_node(node.right, node) + 1;
		if (parent != null)
		{
			return count + 1;
		}
		else
		{
			return count;
		}
	}
	//  Handles the request of printing the euler path
	def euler_path(): Unit = {
		if (this.root == null)
		{
			print("\n Empty Tree \n");
		}
		else
		{
			var ans: Int = euler_path_node(this.root, null);
			print(" Total Node is : " + ans + "\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinaryTree = new BinaryTree();
		/*
				        9
				       / \
				      5   7
				     / \   \
				    1   6   11
				   /   / \   \
				  10  4   8   20
				           \
				            3
				-----------------------
				    Binary Tree
				*/
		tree.root = new TreeNode(9);
		tree.root.left = new TreeNode(5);
		tree.root.right = new TreeNode(7);
		tree.root.left.left = new TreeNode(1);
		tree.root.left.left.left = new TreeNode(10);
		tree.root.left.right = new TreeNode(6);
		tree.root.left.right.left = new TreeNode(4);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.right = new TreeNode(3);
		tree.root.right.right = new TreeNode(11);
		tree.root.right.right.right = new TreeNode(20);
		tree.euler_path();
	}
}

Output

 Total Node is : 21
/*
    Swift 4 Program 
    Find number of node exist in Euler Tour of Binary Tree
*/
//  Tree Node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
//  Binary Tree
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	//  Count the number of nodes in euler path of given tree
	func euler_path_node(_ node: TreeNode? , _ parent : TreeNode? )->Int
	{
		if (node == nil)
		{
			//  When tree node empty
			return 0;
		}
		// Recursively executing the left and right subtree and count nodes
		let count: Int = self.euler_path_node(node!.left, node) + self.euler_path_node(node!.right, node) + 1;
		if (parent != nil)
		{
			return count + 1;
		}
		else
		{
			return count;
		}
	}
	//  Handles the request of printing the euler path
	func euler_path()
	{
		if (self.root == nil)
		{
			print("\n Empty Tree \n", terminator: "");
		}
		else
		{
			let ans: Int = self.euler_path_node(self.root, nil);
			print(" Total Node is : ", ans ,"\n", terminator: "");
		}
	}
}
func main()
{
	let tree: BinaryTree = BinaryTree();
	/*
		        9
		       / \
		      5   7
		     / \   \
		    1   6   11
		   /   / \   \
		  10  4   8   20
		           \
		            3
	-----------------------
		Binary Tree
   */
	tree.root = TreeNode(9);
	tree.root!.left = TreeNode(5);
	tree.root!.right = TreeNode(7);
	tree.root!.left!.left = TreeNode(1);
	tree.root!.left!.left!.left = TreeNode(10);
	tree.root!.left!.right = TreeNode(6);
	tree.root!.left!.right!.left = TreeNode(4);
	tree.root!.left!.right!.right = TreeNode(8);
	tree.root!.left!.right!.right!.right = TreeNode(3);
	tree.root!.right!.right = TreeNode(11);
	tree.root!.right!.right!.right = TreeNode(20);
	tree.euler_path();
}
main();

Output

 Total Node is :  21




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