Questions tagged [tree-traversal]
The tree-traversal tag has no usage guidance.
8
questions
4
votes
0
answers
138
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 ...
- 12.6k
3
votes
1
answer
123
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 ...
- 133
3
votes
1
answer
3k
views
Which Tree traversal String is unique?
Assume we have a tree and we want to serialize it.
Example:
...
- 143
2
votes
1
answer
99
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 ...
- 164
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.
...
- 169
1
vote
1
answer
87
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 ...
- 47
0
votes
1
answer
27
views
Is binary tree balanced if and only if the morris traversal of the tree produces ordered list?
I'm trying to check if the binary tree is binary search tree. My idea is to use Morris traversal. Intuitively a binary tree is balanced iff Morris traversal produces a sorted threaded linked list.
The ...
- 105
0
votes
0
answers
31
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 ...
- 223