Sorting: Ep 08 - Tree Sort

We see how a Binary Tree gives us sorted data!

Category:

Education

Tags:

• sorting
• sort
• algorithm
• algo
• binary
• tree
• computers
• computing

[NeoXC]

How can the algorithm backtrack up, if each node only holds a left and right pointer? This is the part that's confusing me the most. Also, how would the algorithm recognize that the node that it's backtracking up to is the correct one? What is the algorithm for that?

[lcc0612]

@NeoXC

The backtracking is a property of recursive functions. Take for example:

function f(n) print n if n>=1 then f(n-1) end print n + "again!"

end

What happens is that, if i call f(2), f(2) will proceed to call f(1). Notice how, that at this point of time, the first call for f isn't finished yet, but it must wait till f(1) is done, and it will "automatically" backtrack to f(2) to print "2 again!"

Hope this is clear. Look up recursion or leave another comment if you need more help!

[they0killed0kenny]

@lcc0612 I've been having trouble with recursion for a long time, and I always avoid it, but here it seems it can not be left out. Can you recommend any good videos on recursion that would help me understand the binary tree sorting algorithms?

[lcc0612]

@they0killed0kenny

To be honest, I haven't really come across any that's really simple and easy to understand. I'll send you a message if I ever see one.

[meedowi]

Thanks for the help.

[lcc0612]

@meedowi

Cheers! Glad I could be a help!

[cody8092]

Preorder and Inorder are correct. Great Work!

Postorder is incorrect.

The following rule applies to postorder. Postorder will always end with the root.

2 1 4 3 7 8 11 10 9 6 5

Post Order pseudocode

If root is null return

Postorder(left)

Postorder(right)

Postorder(root)

Reference: Java Software Structures by Lewis Chase

[montee322]

Do you have to catch a bus? The video is very fast to understand.

[NeoXC]

@lcc0612 Thank you very much for your reply! I had a simple concept of recursive functions, but never knew that recursive functions return to previous calls. Thanks to you, I now understand how this works :)

[grayman105]

Wow you talk fast!

[mikeye9]

Way too fast....