#1704 added the tsk_tree_preorder and tsk_tree_postorder methods to return an array of nodes in these orders. While these are by far the most important orderings, it would also be nice to support inorder traversal in the library.
Unfortunately, making an iterative inorder traversal algorithm in the general case is quite tricky --- or at least, I haven't been able to figure out how to do it!
While a recursive version is trivial to implement, I don't think we should do this for the library implementation since we can't guarantee safety then (a pathological tree can overflow the stack). Being able to overflow the stack is potentially a security hole, so I'd rather not have an inorder traversal in the C library than one that is insecure.
Anyone fancy an algorithmic puzzle? Here's a version for a binary tree.
If we do add this, we should wire it up to the Python API in the same way that preorder and postorder are done, giving a major boost in inorder traversal perf.
#1704 added the
tsk_tree_preorderandtsk_tree_postordermethods to return an array of nodes in these orders. While these are by far the most important orderings, it would also be nice to support inorder traversal in the library.Unfortunately, making an iterative inorder traversal algorithm in the general case is quite tricky --- or at least, I haven't been able to figure out how to do it!
While a recursive version is trivial to implement, I don't think we should do this for the library implementation since we can't guarantee safety then (a pathological tree can overflow the stack). Being able to overflow the stack is potentially a security hole, so I'd rather not have an inorder traversal in the C library than one that is insecure.
Anyone fancy an algorithmic puzzle? Here's a version for a binary tree.
If we do add this, we should wire it up to the Python API in the same way that preorder and postorder are done, giving a major boost in inorder traversal perf.