CODEWITHSUNDEEP
binary-tree
Hitesh
Hitesh

Reputation: 1228

Recursive VS Nonrecursive for binary tree traversal

What is the differences between Recursive VS Nonrecursive for binary tree traversal?

Which one is best for a large tree and Why?

Thanks

Upvotes: 2

Views: 9263

Answers (2)

itsnickli
itsnickli

Reputation: 41

The difference is that a recursive way uses the call stack whereas an iterative way uses an explicit stack (the stack data structure). What this leads to are two things: 1) If it is a large tree, a recursive way can cause stack overflow. 2) With an iterative approach, you can stop somewhere in the middle of the traversal. In other words, you can implement something like a pre-order/in-order/post-order iterator with a stack. This can be useful in some cases.

Upvotes: 2

Bruno Ferreira
Bruno Ferreira

Reputation: 952

Recursive functions are simpler to implement since you only have to care about a node, they use the stack to store the state for each call.

Non-recursive functions have a lot less stack usage but require you to store a list of all nodes for each level and can be far more complex than recursive functions.

Upvotes: 2

Related Questions