• 0

Compare Two Binary Search Trees


Question

I have been trying to figure out a way to compare two Binary Search Trees without multi-threading or any other such parallel computing means. The goal is to test the equivalence of two Binary Search Trees.

The definition of equivalence here is that the number of nodes must be same, and values contained in the two trees must be equal.

For example, see the attached image for two equivalent trees. Now, how would you test the equivalence of these programmatically?

One method I know of is to traverse the tree using any of the traversal methods - Inorder, Preorder, Postorder, etc. and then compare the results with the other tree's. One may even use a BFS or DFS algorithm.

Any other more efficient ways you can think of doing this?

PS: I am NOT in school. This is NOT a homework assignment. I graduated 3 years ago and I am brushing up on data structures. So please keep an open mind. Thanks!

post-47097-1258666711.png

Link to comment
https://www.neowin.net/forum/topic/847418-compare-two-binary-search-trees/
Share on other sites

9 answers to this question

Recommended Posts

  • 0

it seems that what you really want to know is if they both contain the same nodes since the tree structure can be slightly different and still be balanced.

if you have or can keep a node count in your object that is updated as you add and remove nodes, you could use this as your first check to see if the trees are not equal. if both trees dont have the same number of nodes then you know they're not the same search trees. but having the same node count doesnt mean they are equal, so you can only use node counts to more quickly determine that they're not equal.

the next step if they do have an equal node count would be to traverse one tree and search for that node in the second tree. this should be fairly efficient since you're using search trees. the tree that's traversed would have each node touched once, and the tree being searched is s tree used for searching! at any time in this process if you cant find a node from tree A in tree B you can short circuit the comparison because you know the trees are not equal.

the worst case for this method is when the trees are equal since every node in tree A will have been searched and found in tree B and none of the short circuits would have occurred.

there may be other ways of doing this but this is the first way that popped into my head and it seems pretty good.

  • 0

Interesting! Yes, that sounds like a great solution!

What would be the time complexity of the algorithm you proposed? Is it O(N log N)? N for the tree traversal and log N for the search.

The algorithm in my original post was O(N) + O(N) + O(N) (correct me if I am wrong). However, looking at it from an execution time perspective, it would be slower than O(N log N).

  • 0
  Jebadiah said:
Interesting! Yes, that sounds like a great solution!

What would be the time complexity of the algorithm you proposed? Is it O(N log N)? N for the tree traversal and log N for the search.

The algorithm in my original post was O(N) + O(N) + O(N) (correct me if I am wrong). However, looking at it from an execution time perspective, it would be slower than O(N log N).

Well if I am not mistaken if your algorithm was O(N) then it should be faster no matter what the constants are.

In first case you always have 3*N execution time. So we can roughly say if N > 8 then it's faster than the 2nd algorithm. (I haven't studied any of them).

  • 0

I just got back to this thread. You're right again! In the worst case const * O(N) is better than O(N log N). I just did the calculations with some values of N and came to that conclusion. (Damn! I am so rusty with algorithm analyses now.)

To everyone: any other creative solutions for the original question that you can think of?

  • 0
  Jebadiah said:
That is the solution I talk about in my first post. :)

The preorder and postorder traversals would not produce the numbers in the same order though. And yeah, that seems to be the fastest solution I can currently think of (since it's pretty ****ing fast).

  • 0

function structeq (t1, t2 : tree) : boolean;
begin 
  if t1 = nil										then structeq := t2 = nil
  else if t2 = nil								 then structeq := false
  else if structeq(t1^.left, t2^.left)   then structeq := structeq(t1^.right, t2^.right)
  else												structeq := false
end

That's not my code. But it checks if two tree's have the same structure. To check the values as well you probably need to use "AND" t1.value = t2.value. Probably better to use it with C though, the short-circuited && will come in handy when you want to check the value only if the pointer is not null. (Pascal would require nested if's which is just biah). It's basically what you said, written in Pascal in a neat way.

You can't go any faster than that as far as I know.

  • 0
  gianpan said:
function structeq (t1, t2 : tree) : boolean;
begin 
  if t1 = nil										then structeq := t2 = nil
  else if t2 = nil								 then structeq := false
  else if structeq(t1^.left, t2^.left)   then structeq := structeq(t1^.right, t2^.right)
  else												structeq := false
end

That's not my code. But it checks if two tree's have the same structure. To check the values as well you probably need to use "AND" t1.value = t2.value. Probably better to use it with C though, the short-circuited && will come in handy when you want to check the value only if the pointer is not null. (Pascal would require nested if's which is just biah). It's basically what you said, written in Pascal in a neat way.

You can't go any faster than that as far as I know.

Cool! That way you can check if the two trees are identical in terms of value and structure together in O(N) time. It looks like a Preorder lockstep traversal. Good one!

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Posts

    • It's like I said: people need to bitch about literally anything these days. It's just a freaking stupid thumbnail.
    • Hullucination may be a sign of a more serious condition like schizophrenia or dementia.
    • That trigger travel before actuation is a major turn off for me.
    • This ChatGPT & Automation E-Degree has been price dropped even further by Steven Parker Today's highlighted deal comes via our Online Courses section of the Neowin Deals store, where for only a limited time you can save 97% on this ChatGPT & Automation E-Degree. Immerse yourself in a transformative learning experience with these 12 captivating courses, featuring over 25 hours of engaging content that will redefine the way you perceive the digital landscape. Embrace the future with ChatGPT and unlock the potential of more than 20 indispensable AI tools tailored for today's dynamic challenges in marketing, business, and coding. Embark on a journey of skill enhancement and future-proof your career with our e-degree. Get ready to shape the future with knowledge, innovation, and the best AI tools available today! Access 12 lectures & 25 hours of content 24/7 Explore practical applications & real-world scenarios tailored to your professional domain Gain valuable experience that can be directly applied to your professional endeavors Learn the art of customization as you tailor ChatGPT to meet the unique demands of various industries Unleash your full potential in diverse professional settings Master the art of streamlining business processes through automation, enhancing efficiency, and ensuring optimal resource utilization Gain insights into powerful techniques that transform raw data into compelling visual narratives Discover how AI can amplify your creativity & contribute to groundbreaking projects Elevate your communication skills by mastering conversations with ChatGPT Explore the intersection of AI & data visualization Gray Scale Photo of Gears via PexelsGood to know Length of time users can access this course: lifetime Access options: desktop & mobile Redemption deadline: redeem your code within 30 days of purchase Experience level required: beginner Updates included Certificate of Completion ONLY Lifetime access to the ChatGPT & Automation E-Degree normally costs $790, but you can pick it up for just $19.97 for a limited time, that's a saving of $770 (97%) off the normal price! For full details, terms, and instructor info for the above courses, click the link below. Get this ChatGPT & Automation E-Degree course for just $19.97, or learn more Although priced in U.S. dollars, this deal is available for digital purchase worldwide. We post these because we earn commission on each sale so as not to rely solely on advertising, which many of our readers block. It all helps toward paying staff reporters, servers and hosting costs. Other ways to support Neowin Whitelist Neowin by not blocking our ads Create a free member account to see fewer ads Make a donation to support our day to day running costs Subscribe to Neowin - for $14 a year, or $28 a year for an ad-free experience Disclosure: Neowin benefits from revenue of each sale made through our branded deals site powered by StackCommerce.
  • Recent Achievements

    • Community Regular
      Primey_ went up a rank
      Community Regular
    • Reacting Well
      Gromvar earned a badge
      Reacting Well
    • Dedicated
      BreakingBenjamin earned a badge
      Dedicated
    • Week One Done
      Hartej earned a badge
      Week One Done
    • One Year In
      TsunadeMama earned a badge
      One Year In
  • Popular Contributors

    1. 1
      +primortal
      521
    2. 2
      +FloatingFatMan
      180
    3. 3
      ATLien_0
      166
    4. 4
      Skyfrog
      105
    5. 5
      Som
      98
  • Tell a friend

    Love Neowin? Tell a friend!