Questions tagged [tree-traversal]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer

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 ...
4 votes
0 answers

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 ...
0 votes
0 answers

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 ...
3 votes
1 answer

Which Tree traversal String is unique?

Assume we have a tree and we want to serialize it. Example: ...
3 votes
1 answer

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 ...
1 vote
1 answer

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: The ...
2 votes
1 answer

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 ...
2 votes
2 answers

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. ...