As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [tree-traversal]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
30 views

What type of tree traversal should be performed to obtain the same splay tree?

I'm trying to figure the following: Given splay tree number 1. Perform a tree traversal on it and insert each node into splay tree number 2 in that order. What type of tree traversal should be ...
vesii's user avatar
  • 223
3 votes
1 answer
112 views

Is possible to have a "pointer" to a tree node in a functional language?

Suppose I have the following structure definition in C: struct node { int value; struct node *parent, *left, *right; } If I want to represent a specific ...
matteo_c's user avatar
  • 133
1 vote
1 answer
64 views

Correctness of bft resulting in shortest path

I found the following proof concerning the correctness of a breadth-first traversal resulting in shortest path: source: https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture6.pdf The ...
Tryer outer's user avatar
2 votes
1 answer
96 views

Solution Verification: How does the postorder traversal of a BST change after rotating left?

Given a BST $T$, $x$ is a random node in it and $y$ is the right child of $x$. How does the PostOrder traversal of BST $T$ change after we rotate the tree left on node $x$? In which cases does the ...
Pwaol's user avatar
  • 164
4 votes
0 answers
133 views

Does a priority queue exist with O(1) extract-min and re-insertion from removed positions?

I am envisioning a priority queue that is a bit strange. It represents wanting to do a depth-first left-to-right walk of a tree, but allowing for parallel workers where there can be time between ...
orlp's user avatar
  • 12.5k
3 votes
1 answer
2k views

Which Tree traversal String is unique?

Assume we have a tree and we want to serialize it. Example: ...
Giacomo's user avatar
  • 143
2 votes
2 answers
5k views

Inorder Traversal of the Ternary Tree

As per Wikipedia, Algorithm for In-order Traversal of Binary Tree If the current node is empty/NULL/None return nothing. Traverse the left subtree by recursively calling the in-order function. ...
ankit's user avatar
  • 169