StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
791063
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
9
CommunityOwnedDate
CreationDate
2009-04-26T15:33:50.067
FavoriteCount
0
LastActivityDate
2009-04-27T06:50:07.493
LastEditDate
2009-04-27T06:50:07.493
LastEditorUserId
89806
OwnerUserId
89806
ParentId
791052
PostTypeId
2
Score
1
ViewCount
0
LastEditorDisplayName
text
Body
You can achieve this if nodes have pointers to their parents. When you walk back up the tree (using the parent pointers) you also pass the node you're coming from. If the node you're coming from is the left child of the node you're now at, then you traverse the right child. Otherwise you walk back up to it's parent. EDIT in response to the edit in the question: If you want to iterate through the whole tree, then no this is not possible. In order to climb back up the tree you need to know where to go. However, if you just want to iterate through a single path down the tree then this can be achieved in O(1) additional space. Just iterate down the tree using a while loop, keeping a single pointer to the current node. Continue down the tree until you either find the node you want or hit a leaf node. EDIT: Here's code for the first algorithm (check the iterate_constant_space() function and compare to the results of the standard iterate() function): <pre><code>#include <cstdio> #include <string> using namespace std; /* Implementation of a binary search tree. Nodes are ordered by key, but also * store some data. */ struct BinarySearchTree { int key; // they key by which nodes are ordered string data; // the data stored in nodes BinarySearchTree *parent, *left, *right; // parent, left and right subtrees /* Initialise the root */ BinarySearchTree(int k, string d, BinarySearchTree *p = NULL) : key(k), data(d), parent(p), left(NULL), right(NULL) {}; /* Insert some data */ void insert(int k, string d); /* Searches for a node with the given key. Returns the corresponding data * if found, otherwise returns None.""" */ string search(int k); void iterate(); void iterate_constant_space(); void visit(); }; void BinarySearchTree::insert(int k, string d) { if (k <= key) { // Insert into left subtree if (left == NULL) // Left subtree doesn't exist yet, create it left = new BinarySearchTree(k, d, this); else // Left subtree exists, insert into it left->insert(k, d); } else { // Insert into right subtree, similar to above if (right == NULL) right = new BinarySearchTree(k, d, this); else right->insert(k, d); } } string BinarySearchTree::search(int k) { if (k == key) // Key is in this node return data; else if (k < key && left) // Key would be in left subtree, which exists return left->search(k); // Recursive search else if (k > key && right) return right->search(k); return "NULL"; } void BinarySearchTree::visit() { printf("Visiting node %d storing data %s\n", key, data.c_str()); } void BinarySearchTree::iterate() { visit(); if (left) left->iterate(); if (right) right->iterate(); } void BinarySearchTree::iterate_constant_space() { BinarySearchTree *current = this, *from = NULL; current->visit(); while (current != this || from == NULL) { while (current->left) { current = current->left; current->visit(); } if (current->right) { current = current->right; current->visit(); continue; } from = current; current = current->parent; if (from == current->left) { current = current->right; current->visit(); } else { while (from != current->left && current != this) { from = current; current = current->parent; } if (current == this && from == current->left && current->right) { current = current->right; current->visit(); } } } } int main() { BinarySearchTree tree(5, "five"); tree.insert(7, "seven"); tree.insert(9, "nine"); tree.insert(1, "one"); tree.insert(2, "two"); printf("%s\n", tree.search(3).c_str()); printf("%s\n", tree.search(1).c_str()); printf("%s\n", tree.search(9).c_str()); // Duplicate keys produce unexpected results tree.insert(7, "second seven"); printf("%s\n", tree.search(7).c_str()); printf("Normal iteration:\n"); tree.iterate(); printf("Constant space iteration:\n"); tree.iterate_constant_space(); } </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POIterating over a Binary Tree with O(1) Auxiliary Space
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USmarcog
UserOwnerUserId
1. USmarcog
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.