- Prove that every subtree of a binary search tree is a binary search tree.
ifiok.idiang -2 Newbie Poster
Recommended Answers
Jump to PostBeen there, done that. What's your answer?
Jump to PostThat sounds correct (assuming you've defined a BST accordingly).
If you want to be really anal you should explicitly point out that S is a binary tree.
All 5 Replies
Narue 5,707 Bad Cop Team Colleague
Been there, done that. What's your answer?
Ezzaral 2,714 Posting Sage Team Colleague Featured Poster
Nope. Show some effort if you expect help with your homework.
mrnutty 761 Senior Poster
A hint, read the definition of a binary tree, then see how it applies to the trees's children.
ifiok.idiang -2 Newbie Poster
Proof Let T be a binary search tree, and let S be a subtree of T. Let x
be any element oin S and let TL and TR be the left and right subtrees,
respectively, of x in S. Then since S is a subtree of T, x is also an element
of T, and TL and TR are left and right subtrees of x in T. Therefore,
y x z for every y 2 TL and every z 2 TR. Therefore, S too has the
Binary Search Tree (BST) property.
6
jon.kiparsky commented: Let the guy do his own homework. Give him a hint, not the answer -2
Rashakil Fol 978 Super Senior Demiposter Team Colleague
That sounds correct (assuming you've defined a BST accordingly).
If you want to be really anal you should explicitly point out that S is a binary tree.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.