Check if leaf traversal of two Binary Trees is same or not
The problem "Check if leaf traversal of two Binary Trees is same or not" involves checking whether the leaf nodes' traversal of two given binary trees is the same or not. A leaf node is a node in the tree that does not have any children (i.e., both left and right children are null). The leaf nodes' traversal refers to the sequence of leaf node values encountered while traversing the tree from left to right.
Problem Statement
Given two binary trees, we need to check whether their leaf nodes' traversal is the same or not.
Example
Consider the following two binary trees:
First Binary Tree (x):
6
/ \
7 11
/ \ / \
8 1 5 6
Second Binary Tree (y):
36
/ \
2 17
\ / \
1 5 6
/ \
8 1
Third Binary Tree (z):
36
/ \
2 17
\ / \
1 5 6
/ \
1 8
The leaf traversal for the first tree (x) is [8, 1, 5, 6]
, for the second tree (y) is
[8, 1, 5, 6]
, and for the third tree (z) is [1, 8, 5, 6]
.
Idea to Solve the Problem
To check if the leaf traversal of two binary trees is the same or not, we can use a stack data structure to collect the leaf nodes' data while performing an inorder traversal of each tree. Then, we compare the leaf nodes' data collected for both trees to determine if they are identical.
Algorithm
- Create a stack
s1
and a stacks2
to collect leaf node data for the first and second binary trees, respectively. - Perform an inorder traversal of the first binary tree and collect its leaf nodes' data into
s1
using thegetLeafNodes
function. - Perform an inorder traversal of the second binary tree and collect its leaf nodes' data into
s2
using the samegetLeafNodes
function. - Compare the contents of
s1
ands2
to check if the leaf traversal is the same or not. - Return
true
if the leaf traversal is the same andfalse
otherwise.
Pseudocode
Function isLeafSame(tree1, tree2):
Create an empty stack s1
Create an empty stack s2
Perform inorder traversal of tree1 using getLeafNodes(tree1, s1)
Perform inorder traversal of tree2 using getLeafNodes(tree2, s2)
Initialize a variable result to true
While s1 is not empty and s2 is not empty:
If s1.peek() is not equal to s2.peek():
Set result to false
Pop an element from s1
Pop an element from s2
Return result and check if s1 is empty and s2 is empty
Function getLeafNodes(node, stack):
If node is null:
Return
If node.left is null and node.right is null:
Push node.data onto stack
Return
Recursively call getLeafNodes(node.left, stack)
Recursively call getLeafNodes(node.right, stack)
Code Solution
-
1) Check that two binary tree leaf traversal are same or not in java
2) Check that two binary tree leaf traversal are same or not in c
3) Check that two binary tree leaf traversal are same or not in c++
4) Check that two binary tree leaf traversal are same or not in c#
5) Check that two binary tree leaf traversal are same or not in vb.net
6) Check that two binary tree leaf traversal are same or not in php
7) Check that two binary tree leaf traversal are same or not in node js
8) Check that two binary tree leaf traversal are same or not in python
9) Check that two binary tree leaf traversal are same or not in ruby
10) Check that two binary tree leaf traversal are same or not in scala
11) Check that two binary tree leaf traversal are same or not in swift
12) Check that two binary tree leaf traversal are same or not in kotlin
13) Check that two binary tree leaf traversal are same or not in golang
Time Complexity
The time complexity of the algorithm is O(n) since we traverse each node of both binary trees once, where n is the total number of nodes in both trees. The operations of pushing and popping elements into and from the stack take constant time. Therefore, the overall time complexity is linear.
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