• 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

    • There's absolutely nothing in the WINE license preventing this. Regardless if that sentiment is held by the developers of WINE, it likely doesn't concern the people making Proton nor does it prevent them from adding the support.
    • Multiple competing launchers are unironically a gem on PC gaming—I'm not sure why people don't get that yet. Why replicate Apple's horrible control here? Multiple launchers = multiple stores → lower prices for multi-launcher games Every other con seems minute and irrelevant to a vibrant marketplace where you actually save money. The only real complaints I hear are multiple launchers idle as background tasks + people don't like opening multiple apps. For #1, maybe this OS-based launcher should do shutdown idle launchers like GOG. For #2, virtually all launchers let you create shortcuts. Voila, problem solved.
    • Xbox June Update brings unsynced save management, publisher browsing, and more by Pulasthi Ariyasinghe June has been a busy month for Microsoft, bringing major software upgrades across its product stack. It even announced new hardware for its Xbox lineup, finally entering the handheld gaming space. The company's roundup for this month's new features has now been published, and it's touting a great deal of changes. To start off on the PC side, the Xbox app on the platform now has a section to browse by publishers. The company says that this will let players easily discover more games made by their favorite developers and franchises. Copilot for Gaming also landed in beta form recently, letting users ask AI for help when a game gets too difficult. It's only available for iOS and Android for now, with ROG Xbox Ally support coming later this year. Another feature that will hit the Xbox Ally is the new universal launcher feature for the Xbox app on PC. Microsoft just kicked off Xbox Insider testing for this functionality earlier today. Get all the details here. Over on consoles, the ability to hide system apps, pin favorites to the list, and reduce the number of tiles displayed are now available. Game Hubs also arrived as a fresh feature to easily display relevant information when selecting a game to play, offering data on player stats, achievements, friends currently playing, recent captures, available add-ons, events, and more. Double-tapping the play button will quick-launch the game instead. On both Xbox consoles and in the cloud, a new progress bar will now appear when a save has been left behind on a device in an offline state. "A new progress bar, device names, timestamps, and additional details are now displayed when you have previous game saves on another device in an unsynced state," says the company. Microsoft has also added mouse and keyboard controls as well as touch controls for more cloud games this month. These join the fresh additions that have landed on the 'Stream your own game' collection and the Retro Classics app. Check out the full lists on the announcement page here. On top of all this, Microsoft has also announced that Xbox will be at Gamescom this year. While no details have been announced yet, more announcements from Xbox Game Studios may happen at the major gaming event.
    • Hopefully this is a precurser to them linking other launchers to the Xbox console. With this current gen the Xbox has had dismal sales compared to the competition. If they did support Steam, Epic, Ubisoft Connect, etc etc they'd crush on the next gen battle.
    • My update. Didn't see much point in the top panel since global menu isn't there, so going with a win/kde layout now. Overall, I would say Gnome is a disappointment - it's been 15 years and you still have to rely on a bunch of extensions to get anything useful out of it. At the same time, the way Universal Blue / Bluefin is approaching the desktop feels like what Ubuntu should have started doing five years ago (no wonder the guy I learned about this from used to work for Canonical). Maybe I should have gone with Aurora (the KDE variant), or Bazzite with KDE, but I think I have Gnome where it works for me now.       
  • Recent Achievements

    • Dedicated
      Camlann earned a badge
      Dedicated
    • Week One Done
      fredss earned a badge
      Week One Done
    • Dedicated
      fabioc earned a badge
      Dedicated
    • One Month Later
      GoForma earned a badge
      One Month Later
    • Week One Done
      GoForma earned a badge
      Week One Done
  • Popular Contributors

    1. 1
      +primortal
      647
    2. 2
      Michael Scrip
      225
    3. 3
      ATLien_0
      220
    4. 4
      +FloatingFatMan
      144
    5. 5
      Xenon
      136
  • Tell a friend

    Love Neowin? Tell a friend!