CODEWITHSUNDEEP
algorithmlinked-listbinary-tree
Hormigas
Hormigas

Reputation: 1449

Linked List in Binary Tree

I'm trying to solve : https://leetcode.com/contest/weekly-contest-178/problems/linked-list-in-binary-tree/

I have the following solution : 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean ans;
    ListNode originalHead;
    public boolean isSubPath(ListNode head, TreeNode root) {
        this.ans = false;
        originalHead = head;
        traverse(head, root);
        return ans;
    }

    public void traverse(ListNode head, TreeNode root) {
        if(head == null) {
            ans = true;
            return;
        }
        if(root == null) return;

        if(!ans && root.val == head.val) traverse(head.next, root.right);
        if(!ans && root.val == head.val) traverse(head.next, root.left);
        if(!ans) traverse(originalHead, root.right);
        if(!ans) traverse(originalHead, root.left);
    }
}

I'm wondering if this solution has a time complexity of O(n^2) or not. I ask this since I'm encountering a Time Limit Exceeded error for one of the test cases in the test suite.

I do see other O(n^2) solutions passing though.

Appreciate any help.

Thank you!

Upvotes: 0

Views: 245

Answers (1)

ruakh
ruakh

Reputation: 183301

If n is the number of vertices in the tree, then your algorithm's worst-case time complexity is in Θ(2n) rather than O(n2).

This worst case occurs when every non-leaf node of the tree has just one child, the linked list is longer than the tree is deep, and all of the nodes in the tree and the linked list all have the same value. When that happens, you end up making all of your recursive calls — your if-conditions are always met — so each time you call traverse on a node, you call traverse twice on its child node. So you call traverse once on the root node, twice on its child, four times on its grandchild, eight times on its great-grandchild, etc., which is Θ(2n) if there are n nodes.

Upvotes: 1

Related Questions