• 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

    • Here are all the new features added to Microsoft 365 Copilot in June 2025 by Usama Jawad Towards the end of each month, Microsoft publishes a roundup of the features that it added to some of its popular software in the previous four weeks. We have already talked about the new capabilities introduced in Excel and Teams during the month of June 2025, and now, it's time to talk about Microsoft 365 Copilot. We'll start off with admin-facing capabilities since there are only a few of them. For starters, the usage metrics for Copilot in the Copilot Analytics tool now have new prompt categories that give more insights as to how users are engaging with Copilot. This feature has just begun rolling out, but another enhancement to the usage metrics that is already available is dedicated statistics for intelligent meeting recaps. Finally, Microsoft 365 admins can now view and manage their inventory of agents and connectors and also have more granular control over costs and billing policies. On the user side of things, we have intelligent assistance in Copilot Chat, powered by ContextIQ. This layer of intelligence can scope prompts to internal (SharePoint, OneDrive) and external data sources, find files in the chat, and proactively offer relevant suggestions as you type. In the same vein, the Copilot mobile app is being updated so you can talk to the AI in a natural manner using your voice. In addition, users can also get access to deep reasoning agents such as Researcher and Analyst for more complex and research-oriented needs. The Create experience in the app is also being updated with the ability to generate stories and branded templates. Other interesting Copilot capabilities rolling out to Edge customers are the ability to prompt the AI through the search bar, access agents from within the browser, and take advantage of Copilot's impressive text summarization capabilities. That's not all though, other features in tow include: Enhancements to Copilot in Outlook: Schedule meetings through Copilot chat, summarization of email attachments, a new sidebar experience in the classic Outlook app, meeting preparation, and automated meeting invite creation Improved image generation and large file handling in Copilot Chat: More photorealistic image generation with better text depiction, ability to generate longer summaries from bigger files, and PDF scanning capabilities for insights Memory in Copilot: Copilot will now remember certain items from your conversation and you can modify or delete them Transferred calls summary with Copilot in Teams Phone: Generate a summary of a call and transfer it to a target New file extension for Copilot Pages: Copilot Pages will now have .page extension with an updated file icon Copilot Notebooks availability in OneNote: We already covered this in detail here Seamlessly add brand-approved images with Copilot in PowerPoint: Integration of Copilot with SharePoint Organization Asset Library (OAL) and Templafy asset libraries Explain formulas on the grid with Copilot in Excel: Self-explanatory, exactly what it says on the tin Expanded availability for the Microsoft 365 Copilot app: Availability of the Microsoft 365 Copilot app on Mac You can read more details about each of the aforementioned features here.
    • Damn, I blocked OldGuru a long time ago and you have to go and quote them so I have to read that creepy a$$ take. LOL Anyway 100% that dude can't find women that will have sex with him.
    • OneNote for Windows gets support for Dynamic DPI by Usama Jawad OneNote for Windows (part of Microsoft 365) is a pretty useful app if you're actively engaged in note-taking activities and also appreciate some rich text formatting capabilities. In fact, it also offers some decent integrations with Copilot, which make it an important piece of software in productivity-based environments. Now, Microsoft has introduced a feature that will likely make people with multi-monitor setups very happy. The OneNote for Windows application now supports Dynamic DPI (dots per inch). What this means is that you can use OneNote across any screen and it will scale according to the display's resolution, and you won't get a disconcerting and distracting blurring effect. You can extend your display to a high-resolution monitor and shift OneNote across displays without a hitch or any distraction. This is similar to the UX that is already present in Word, Excel, and PowerPoint. This Dynamic DPI support not only extends to the main text area but also to the section tabs, the Notebooks pane, drop-down menus, and Copilot Notebooks. All of these should look crisp and polished moving forward, without any manual adjustment or even an app restart required from the user's side. Microsoft has highlighted that it was encouraged to work on this capability after receiving user feedback from customers in this area. Dynamic DPI is now available to Current Channel (CC) customers on OneNote for Windows, running Version 2504 (Build 16.0.18827.20042) or later. That's not all, though. Another smaller enhancement present in OneNote moving forward is a revamped setup experience when you launch OneNote on a new Windows device for the first time. You will now receive a list of your five most recently used (MRU) notebooks that will open instantaneusly with a click. If you have more than five notebooks, you can pick and choose the files that you want to open. That said, Microsoft is looking to expand and improve on this experience in the future since it is fairly limited right now.
    • I'll buy one when that add an M chip.
    • Apple iPad Mini is back to its lowest price, saving you $100 by Fiza Ali Amazon US is once again offering the Apple iPad mini at its lowest price, so you may want to check it out. The iPad mini offers an 8.3‑inch Liquid Retina display which delivers a 2266×1488 pixel resolution at 326 ppi. It further supports P3 wide colour, True Tone, an anti‑reflective coating, and achieves up to 500 nits of brightness. At its core sits the A17 Pro chip, which comprises a six‑core CPU (two performance cores and four efficiency cores), a five‑core GPU, and a 16‑core Neural Engine. Hardware‑accelerated ray tracing is supported for advanced graphics, and the Neural Engine accelerates machine learning tasks. When it comes to the device’s camera system, video calls and selfies are handled by the 12MP Ultra Wide front camera with Centre Stage, while the 12MP Wide rear camera with True Tone flash captures photos, scans documents, and records 4K video. Moreover, the iPad mini features dual microphones for calls, video capture, and audio recording, alongside landscape‑oriented stereo speakers that deliver clear, immersive sound. The iPad mini supports both Apple Pencil Pro and Apple Pencil (USB‑C). It also includes Apple Intelligence, a personal intelligence system that assists with writing, creative expression, and productivity. Finally, wireless connectivity comprises Wi‑Fi 6E (802.11ax) with simultaneous dual‑band, Bluetooth 5.3, and sub‑6 GHz 5G and Gigabit LTE. Touch ID is also integrated into the top button, enabling secure fingerprint authentication for unlocking, app sign‑in, and Apple Pay. Apple iPad mini (A17 Pro): $549 (Amazon US) - 15% off This Amazon deal is US-specific and not available in other regions unless specified. If you don't like it or want to look at more options, check out the Amazon US deals page here. Get Prime (SNAP), Prime Video, Audible Plus or Kindle / Music Unlimited. Free for 30 days. As an Amazon Associate, we earn from qualifying purchases.
  • Recent Achievements

    • Week One Done
      dennis Nebeker earned a badge
      Week One Done
    • One Year In
      timothytoots earned a badge
      One Year In
    • One Month Later
      CHUNWEI earned a badge
      One Month Later
    • Week One Done
      TIGOSS earned a badge
      Week One Done
    • First Post
      henryj earned a badge
      First Post
  • Popular Contributors

    1. 1
      +primortal
      464
    2. 2
      +FloatingFatMan
      195
    3. 3
      ATLien_0
      163
    4. 4
      Xenon
      77
    5. 5
      Som
      73
  • Tell a friend

    Love Neowin? Tell a friend!