Given two n-ary trees, check if they have the same leaf nodes from left to right.

  • 1

    If we are given two n-ary trees check if the leaf nodes are the same in the left to right direction.

  • 2

    So basically we need to get a string of leaf nodes of both the trees and if both the strings are equal then return true
    Now by definition, leaf node is a node who doesn't have any children so to get list of leaf nodes of a tree, while doing a DFS traversal if we find a node which has an empty list of children then append it's data to our result string. This way we can get string of leaf nodes

    Code can something as below. Let me know if there is anything wrong in this solution.
    Time complexity is O(|V|), as we need to traverse all nodes.
    Space complexity - since it is a recursive implementation it would be O(h)

    class tNode{
        char data;
        ArrayList<tNode> children;
        public tNode(char c){
            data = c;
            children = new ArrayList<tNode>()
    public boolean hasSameLeafNodes(tNode root1, tNode root2){
    		StringBuilder s1 = getLeafNodes(root1);
    		StringBuilder s2 = getLeafNodes(root2);
    		return s1.equals(s2);
    public StringBuilder getLeafNodes(tNode r){
    		if(r == null)
    			return null;
    		StringBuilder sb = new StringBuilder();
    		ArrayList<tNode> list = r.children;
    		if(list.size() >0){
    			for(int i=0;i<list.size();i++){
    		return sb;

  • 0

    @ratnanireshma this wont work.
    let say root1 has [32, 3] and root2 has [3, 23] as leaves, your solution uses string repr and "323" equals "323" will return true but is incorrect.

Log in to reply

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