Questions tagged [tree-traversal]
The tree-traversal tag has no summary.
9 questions
1
vote
1
answer
72
views
What do you call the two most common ways of selecting a random leaf node from a tree?
If you have a tree, there are two common ways to select a random leaf node from the tree:
You can "flatten" out the tree, so that each leaf node gets selected with the same probability.
...
- 11
2
votes
1
answer
240
views
Tree algorithm - arrange integer array numbers to form largest number
I have solved leetcode's Largest Number.
I am asking another question about it here, more from a theory perspective about "if" I had used a tree for the solution. I have a full functioning ...
- 123
0
votes
1
answer
92
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
3
votes
1
answer
197
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 ...
- 203
1
vote
1
answer
207
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 ...
- 59
2
votes
1
answer
172
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
4
votes
0
answers
215
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 ...
- 14k
3
votes
1
answer
4k
views
Which Tree traversal String is unique?
Assume we have a tree and we want to serialize it.
Example:
...
- 143
2
votes
2
answers
7k
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.
Display ...
- 169