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.
Posts
Showing posts from April, 2021