-

   Basic Things of a Binary Tree

1. Check if a Binary Tree is a subtree of another Binary Tree (একটি বাইনারি ট্রি অন্য একটি বাইনারি ট্রি এর সাবট্রি কিনা চেক করা )
Suppose we have a main Binary Tree M  and another Binary Tree S.  We have to check if S is a subtree of M or not.

Solution: Tree S is a subtree of M if both inorder and preorder traversals of S are substrings of inorder and preorder traversals of M respectively ( ট্রি S, ট্রি M এর সাবট্রি হবে যদি S এর ইনঅর্ডার এবং প্রিঅর্ডার ট্রাভার্সেল  M এর ইনর্ডার এবং প্রিওর্ডার ট্রাভার্সেল এর সাবস্ট্রিং হয় ).

The above algorithm doesn't work for cases where a tree is present
in another tree, but not as a subtree. Handle this case by adding a special character whenever we encounter NULL in inorder and preorder traversals.

Comments

Post a Comment

Popular posts from this blog

URI 2994 Solution

-
URI 2994 - How much earn a Doctor?  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 SELECT d . name , ROUND (t . salary, 1 ) FROM doctors as d INNER JOIN ( SELECT id_doctor, SUM( (hours * 150 ) + ((hours* 150.0 * w . bonus) / 100.0 ) ) AS salary FROM work_shifts AS w INNER JOIN attendances AS a ON w . id = a . id_work_shift GROUP BY id_doctor ) AS t ON t . id_doctor = d . id ORDER BY t . salary desc ;
Read more

URI 2996 Solution

-
 URI 2996 - Package Delivery 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 SELECT year , sender, receiver FROM packages AS p INNER JOIN ( SELECT id_package, name AS sender FROM packages INNER JOIN users ON id_user_sender = id WHERE address <> 'Taiwan' ) AS sub1 ON sub1 . id_package = p . id_package INNER JOIN ( SELECT id_package, name AS receiver from packages INNER JOIN users ON id_user_receiver = id WHERE address <> 'Taiwan' ) AS sub2 ON sub2 . id_package = p . id_package WHERE color = 'blue' OR year = 2015 ORDER BY year DESC , sender DESC ;
Read more