Thread: preorder traverse

Originally Posted by RyanC

I'm confused about term "root" , is in't it mean just the first root of the whole tree? if so then how preorder consider every sub-tree is a new root?

Every non-empty tree has a root. A subtree is a tree, so it has a root different from the root of the overall tree.

Originally Posted by RyanC

and how PC knows that's now we have sub-tree .. ?

It's not the "PC". It's you writing the code such that you keep track of the root of each subtree, e.g., in a recursive function it could be a parameter.

Originally Posted by RyanC

So how is that done? I mean how the PC/SOFTWARE know we are in subtree so it's a tree etc .. I mean how the PC thinks like us?! how the PC knows that we are now in a new subtree so we have new tree?

Usually, a recursive function written to work with tree wouldn't "know" it is dealing with a subtree, and it shouldn't have to: it just handles a tree, and if it so happens that a subtree was passed to it, great! Still works either way.

Originally Posted by RyanC

who said that every subtree is a tree? how do you make that conclusion ?

That's by definition of "subtree": The tree which is a child of a node.

Originally Posted by RyanC

lets say I have fully tree with node X yeah? I call a function by node X so the root is X .. yup? that's fine!!!
in another time I called one of the child of node X lets say it's y, so if I call a function with node y, the new root is y, my question why "y" called new root?! I mean how does the PC know now I've new root? and how he's assign it as root and not a node?!

Let's consider a concrete example: a binary tree denoted by a pointer to its root node, and a simple recursive function for computing the height of the binary tree:

Code:

struct node
{
    struct node *left;
    struct node *right;
};

size_t compute_height(struct node *root)
{
    if (!root)
    {
        return 0;
    }

    size_t left_subtree_height = compute_height(root->left);
    size_t right_subtree_height = compute_height(root->right);
    return 1 + ((left_subtree_height > right_subtree_height) ? left_subtree_height : right_subtree_height);
}

So, we see that in the compute_height function, the root parameter is initially called with the root of the overall tree. But wait, if the tree is not empty, we call compute_height(root->left). In this recursive call, the compute_height function's argument is root->left, which means that the parameter root in this recursive call corresponds to the argument root->left, i.e., from the perspective of this recursive function call, root->left is the root of the tree. This tree is actually a subtree, but from the perspective of the recursive function call, it might as well be the overall tree.

That's the key to recursive thinking here: a subtree is a tree, so whatever can be done with a tree, can be done with a subtree. A tree has a root; a subtree has a root. What's the height of a binary tree? 0 if the tree is empty, otherwise it's 1 + the height of the taller of its two subtrees. How do we compute the height of the subtrees? They are trees, so recursively apply this function to compute the height of a tree, i.e., for one recursive call, the root is the root of the left subtree, and for the other recursive call, the root is the root of the right subtree.