• 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

    • Mixed news. Glad to hear LibreOffice is catching up to MS's Office. The latter has become way too bloated/complicated and non-intuitive to non-power users. Apparently, MS no longer cares for the non-gaming home-based consumer. Sad to hear support for WIndows-7 is ending. Many users remain with Windows-7 as it was easy to use, intuitive, and reliable. Non-power users and gamers don't need to needless complexity, dubious "features," and long-term instability of the last few versions. [After "how many years" Windows-10 is now reasonably stable--as long as MS stops mucking with it.]
    • Yeah but Microsoft actually did a good job with Aero Glass. I remember the only complaints was about how people could not use it without a top tier card back in the day, it would also disable until you activated Windows. Aero Glass was used in window borders, taskbar and yes the Start menu, but only as a border reference, the programs in the Start menu had a black background on Start (if I remember correctly) and All Programs and context menus were not glass.
    • The only thing it looks like to me is harder to read.
    • I am surprised that the kid who got run over next to stop light did not sue...
    • Wine 10.10 released, brings updated Mono engine, bug fixes for several games, and more by David Uzondu Nearly two weeks after Wine 10.9 dropped, Wine 10.10 is here with an updated Mono engine and the complete removal of a major graphics dependency. The Wine Mono engine, which provides .NET Framework support, has been bumped to version 10.1.0. Another major change is the removal of the OSMesa library as a dependency. OpenGL rendering on memory device contexts will now be handled by a pbuffer, cleaning up the graphics stack. Here are other notable changes with this release: More support for generating Windows Runtime metadata in WIDL. Locale data updated to Unicode CLDR 47. P010 format support in Media Foundation. Of course, no development release would be complete without a boatload of bug fixes. This version crushes a total of 38 bugs, addressing problems in a wide range of applications and games. Gamers will be pleased to see fixes for titles like F.E.A.R., S.T.A.L.K.E.R.: Anomaly, and StarCraft Remastered. Issues that caused a black screen in Steam's Big Picture mode and crashes when starting a new game in F.E.A.R. have been resolved. The fixes go way back, even tackling issues in ancient software like Lotus Freelance Graphics 2.1 and input problems in the classic indie game Braid. Here's the full list of game-related issues addressed: Rise of Nations: Both mouse buttons were required for a single left-click Braid: Both Shift keys needed to move puzzle pieces F.E.A.R: Crashed with an "Out of memory" error when starting a new game F.E.A.R Combat: Black screen at startup due to memory error S.T.A.L.K.E.R. Anomaly: Crashed when loading into a save file StarCraft Remastered: Game wouldn't start with Wine 10.5 Unreal II: Hangs with a black screen when switching to 1440x900 resolution Eador. Masters of the Broken World: Bad map textures after starting the game Horizon Chase: Freezes on startup The Fidelio Incident and Vampyr: Beeping noise on exit Burger Shop: Shifted to the top left corner in fullscreen mode And here's the rest of the issues that were fixed: Lotus Freelance Graphics 2.1: Hangs at the splash screen HTML-Kit 292: Tab bar isn't fully visible without scrolling at 96 DPI Tab completion for cmd: Improvements made regedit: Binary values editor layout is broken and .reg files couldn’t be imported Baofeng5-5.31.1128: Welcome window crashes on start Canon printer driver installation now works Steam Big Picture mode: Fixed black screen when using d3d10 Noteworthy Composer: Crashes in winealsa resolved Ricoh Digital Camera Utility 5: Crashes when switching between Browser and Laboratory modes Wondershare Uniconverter 13: Characters now display properly AVCLabs Video Enhancer AI: No longer crashes on start New thread stack memory usage optimized PlayOnline Viewer: Window now properly activates after being minimized Virtual desktop behavior fixed secur32:ntlm tests now pass on Windows 11 24H2 d3d9:device WM_WINDOWPOSCHANGED test no longer fails on Linux GitLab CI no longer crashes in various multimedia tests HP Prime Virtual Calculator: Fixed startup crash Qt Installer for Windows: Now functions correctly SHIFT-based range selection logic corrected Creating 64-bit wineprefix with old wow64 now possible Regression from realloc switch fixed (memory now zeroed as expected) RTTI now works on arm32 after recent changes Smartsuite 3.1 installer no longer crashes Fixed possible use-after-free in dbghelp's symt_add_func_line Build issues with clang for x86_64 resolved due to RTTI changes You can read the full release notes here. The source code for this release is also available. To get started, follow the installation instructions for your platform: Ubuntu/Debian, Fedora, or macOS.
  • Recent Achievements

    • Week One Done
      Simmo3D earned a badge
      Week One Done
    • One Month Later
      Simmo3D earned a badge
      One Month Later
    • One Month Later
      greege earned a badge
      One Month Later
    • Week One Done
      greege earned a badge
      Week One Done
    • Week One Done
      LagFighterZ earned a badge
      Week One Done
  • Popular Contributors

    1. 1
      +primortal
      547
    2. 2
      ATLien_0
      232
    3. 3
      +FloatingFatMan
      165
    4. 4
      Michael Scrip
      119
    5. 5
      +Edouard
      91
  • Tell a friend

    Love Neowin? Tell a friend!