• 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

    • Arlo Essential 2K Indoor Camera: Unpacking the features and value of this home security cam by Paul Hill Are you in the UK and looking for internal cameras to keep an eye on your pets or property? If so, the Arlo Essential 2K indoor security camera (2-pack) is now discounted by 26% from its £159.99 RRP to just £119.00. As usual, the product is available with free delivery and free returns, which is helpful if the product turns out to be defective. In addition to the discounted product, the listing also notes there’s a £10-off voucher available until Monday and a £10 Morrisons on Amazon voucher. Arlo is a reputable brand for home security cameras so this deal marks a great opportunity if you’ve been looking for this type of device. Do note that it is a wired camera so it’ll have to be plugged in somewhere. Deep dive into camera features and capabilities The Arlo Essential 2K indoor security camera comes with a very good 2K (up to 2,560x1,440) resolution that provides you with clear, detailed video, great if you want to keep an eye on smaller pets such as kittens. Not only is the camera high-quality, but the camera is equipped with black and white night vision (it can see up to 7 metres), so you can see any events that occur at night. This Arlo security cam features two-way audio with noise reduction and echo cancellation allowing you to chat with anyone coming to feed your pets. There’s also an automatic privacy lens cover that physically blocks the lens when disarmed, providing you with more privacy when at home. There is also passive infrared motion detection that has a range of 7 metres. You can use motion detection in combination with the 80 dB smart siren to scare away intruders. The siren can also be activated manually. The Arlo Essential 2K features a 130-degree wide-angle diagonal view, which is sufficient for most rooms, to capture more of what’s going on in the room and there is 12x digital zoom to take a closer look at objects. It’s compatible with pretty much all Wi-Fi devices with its 2.4GHz Wi-Fi support and it integrates with your smart home via Amazon Alexa, Google Assistant, and IFTTT. Leveraging the Arlo Secure subscription for enhanced security When you buy the Arlo Essential 2K, you get a 30-day free trial of the Arlo Secure subscription, and if you want to continue it, it costs from £11.99 per month or £119.90 per year. This subscription isn’t necessary for basic functionality, but it does unlock the full potential of the camera. When you subscribe you get secure cloud storage for video history (30 to 60 days depending on plan); AI-powered identification of people, animals, vehicles, and packages, reducing false alerts; custom activity zones that let you define areas for motion detection, minimising unwanted notifications; and interactive notifications that can be interacted with from the lock screen like view animated previews, activate siren, and call emergency services. My biggest issue with this camera is that there is no local storage for recordings, necessitating the need to buy the subscription if you want to save any footage. If you’re thinking of using this camera to protect your home from theft and want footage to give to the police, you’ll need a subscription. An alternative to a subscription is buying the Arlo SmartHub (VMB5000) which is compatible with the Arlo Essential 2K indoor camera, according to Arlo’s website. The savings on this camera twin-pack are significant and it’s the lowest price they’ve been at on Amazon UK so they’re definitely worth considering for your home. If you don’t mind the subscription or have the Arlo SmartHub already, then this camera makes sense. If not, then you may be better off with a camera that comes with an SD card slot and recording capabilities. Arlo Essential 2K Indoor Pet Security Camera (2-pack): £119 + £10-off voucher + £10 for Morrisons on Amazon (Amazon UK) / MSRP £159.99 This Amazon deal is U.K. 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 UK deals page here. Get Prime, Prime Video, Music Unlimited, Audible or Kindle Unlimited, free for the first 30 days As an Amazon Associate we earn from qualifying purchases.
    • The Nokia Lumias? Or the third-party HTC One8's? I had HTC's hardware cuz it was slick and reliable... but, yeah, the software left me wanting more and I just couldn't allocate personal time to develop all of the software I would have wanted to see (overworked in other capacities @ MSFT at the time, heh).
    • Microsoft's mobile strategy had great future vision and UX research, but mediocre engineering and inadequate support (third-party and internal business alike). The death knell for WinMo was Google's (mostly YouTube's) incessant API blocking and purposeful release of buggy WinMo builds to force consumers to stay away -- and this was conducted via sabotage of whatever partnerships they were supposed to play nice in. I still yearn for that UI on a modern smartphone...
    • Linux has always been an option but never adopted by the masses despite being free. The reasons are limited usability and features. Despite everything we all complaint about with MS , the overall experience for the general public is much better than what Linux can deliver.
    • If nothing works automatically for you, I'd say pick a better/different distro. Granted, it's trickier with laptops because they use all kinds of weird hardware, but still. I actually just did a fresh Arch Linux install on my netbook, and given that Arch is certainly not an "automagical" distro, I had to do very little manual tweaking, everything but the audio worked out of the box (including plasma and Wayland) and the audio was simply an issue of installing an additional firmware package that wasn't included in the default selection. Which is equivalent of installing additional drivers in Windows. Surely a more user-oriented distro would be even less troublesome (but granted, I haven't used/tested anything outside of Arch for quite some time). And let's not forget that a fair bit of issues that get blamed on Linux (though it also applies to Windows issues) are actually caused by hardware vendors not giving a damn.
  • Recent Achievements

    • One Month Later
      POR2GAL4EVER earned a badge
      One Month Later
    • One Year In
      Orpheus13 earned a badge
      One Year In
    • One Month Later
      Orpheus13 earned a badge
      One Month Later
    • Week One Done
      Orpheus13 earned a badge
      Week One Done
    • Week One Done
      serfegyed earned a badge
      Week One Done
  • Popular Contributors

    1. 1
      +primortal
      563
    2. 2
      ATLien_0
      256
    3. 3
      +Edouard
      163
    4. 4
      +FloatingFatMan
      157
    5. 5
      Michael Scrip
      109
  • Tell a friend

    Love Neowin? Tell a friend!