First pair of mismatching leaf nodes


  • 1
    B

    Print first pair of mis-matching leaves (first pair as in in-order) given two pre-order traversal arrays of BSTs.
    [5,4,2,4,8,6,9] and [5,3,2,4,8,7,9]

    1. Can we solve this problem without building the tree ?. The main problem is how do we identify the leaf nodes ?.

  • 0
    H
    This post is deleted!

  • 0
    U

    create two preorder iterators on the trees. then you can compare the iterators' output one by one.


  • 0
    B

    @ulyx Could you please give some code example
    Thanks


  • 0
    D

    Can you please state the question more clear?


  • 0
    V

    intern or full time position?


  • 0
    A

    for example:
    if(a[i]!==b[i] && a[i+1]<a[i] && b[i+1]<b[i] && a[i+2]>a[i] && b[i+2]>b[i])
    then a[i+1] and b[i+1] are the first mis-matching leaves.And they are left leaf nodes.


  • 0
    V
    This post is deleted!

  • 0
    V

    @asurily what about right leaf nodes?


  • 0
    V

    I have implemented code to get the leaf nodes, works for most cases, still not confident though,

    Basic Idea : Push nodes into the stack if it is lesser than top stack element.
    else, store the top(call it x) and pop it, and store the next top(call it y) as well, keep popping from the stack until stack's top becomes greater than current element.
    If the stack's is not y, then x is a leaf node.

    We basically check if the next node can be the left or right node of the parent(stack's top), checking left is trivial, to check right, if after removing elements the top is y, then the new node will go to x's right, so x is not a leaf node.

    Can someone verify the idea/code? Seems to work for most cases.

    #include <iostream>
    #include <vector>
    #include <stack>
    using namespace std;
    
    
    void getLeafNodes(vector<int>& nums, vector<int>& result)
    {
        if(nums.size()==0)
            return;
        stack<int> repo;
        int i=0;
        while(i<nums.size())
        {
            if(repo.empty())
            {
                repo.push(nums[i]);
                i++;
            }
            else
            {
                if(nums[i]<repo.top())
                {
                    repo.push(nums[i]);
                    i++;
                }
                else
                {
                    int top = repo.top();
                    repo.pop();
                    if(!repo.empty())
                    {
                        int top2 = repo.top();
                        while(!repo.empty() && nums[i] > repo.top())
                        {
                            repo.pop();
                        }
                        if(repo.empty() || top2 != repo.top())
                        {
                            result.push_back(top);
                        }
                    }
                    repo.push(nums[i]);
                    i++;
                }
            }
            
        }
        if(!repo.empty())
        {
            result.push_back(repo.top());
            repo.pop();
        }
    }
    
    
    int main() {
        
        
        int a[] = {890,325,290,530,965};
        //int a[] = {3};
        //int a[] = {10,20,40,30};
        vector<int> nums(a,a+5);
        vector<int> result;
        getLeafNodes(nums,result);
        for(int i=0;i<result.size();i++)
            cout<<result[i]<<" ";
        cout<<endl;
        
        
       
    	return 0;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.