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

1. Create a stack s1 and a stack s2 to collect leaf node data for the first and second binary trees, respectively.
2. Perform an inorder traversal of the first binary tree and collect its leaf nodes' data into s1 using the getLeafNodes function.
3. Perform an inorder traversal of the second binary tree and collect its leaf nodes' data into s2 using the same getLeafNodes function.
4. Compare the contents of s1 and s2 to check if the leaf traversal is the same or not.
5. Return true if the leaf traversal is the same and false 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.