For Red-Black tree (balanced tree) preorder/inorder/postorder traversal, which involves depth first scan, 2 * log(n) additional space is required ([1]). [1] He

For Red-Black tree (balanced tree) preorder/inorder/postorder traversal, which involves depth first scan, 2 * log(n) additional space is required ([1]). [1] Here is an example, look for st_tr_aux() function: https://github.com/faragon/libsrt/blob/master/src/stree.c https://github.com/faragon/libsrt/blob/master/src/stree.c