CODEWITHSUNDEEP
javaalgorithmtreebinary-tree
shrinidhisondur
shrinidhisondur

Reputation: 759

How is this program a pre-order traversal?

int count(Node node) {

  if (node == null)
      return 0;

  int r = count (node.right);
  int l = count (node.left);

  return 1 + r + l;
}

This function returns number of nodes in Binary Tree rooted at node. A few articles say this is a pre-order traversal, but to me this looks like a post-order traversal, because we are visiting the left and the right parts before we visit the root. Am I wrong here ? Or is my notion of "visited" at fault ?

Upvotes: 1

Views: 384

Answers (4)

Ted Hopp
Ted Hopp

Reputation: 234795

In this code, no actual processing is being done at each node, so there would be no difference between a pre-order and post-order traversal. If there were processing, the difference would be:

pre-order

int count(Node node) {

  if (node == null)
      return 0;

  process(node);    

  int r = count (node.right);
  int l = count (node.left);

  return 1 + r + l;
}

post-order

int count(Node node) {

  if (node == null)
      return 0;

  int r = count (node.right);
  int l = count (node.left);

  process(node);    

  return 1 + r + l;
}

(Actually, in these cases—unlike with your code—you'd probably want to recurse on node.left before node.right to preserve the conventional left-to-right ordering of processing children.)

Upvotes: 4

Abhi
Abhi

Reputation: 744

Yes. Your notion of visited is wrong! Here visited means that you are at current node and then trying to traverse the tree. Counting is done at 'root' first then ur counting rights and then lefts so yes it is preorder.

Upvotes: 1

przemek hertel
przemek hertel

Reputation: 4004

Counting nodes is case in which it is hard to say if algorithm is pre-order or is post-order because we don't know "when" we "count" 1 for current node.

But if we change case to printing it becomes clear:

pre-order:

int visit(Node node) {
  ...
  node.print();          // pre-order  : root cames first
  visit(node.left);
  visit(node.right);
  ...
}

post-order

int visit(Node node) {
  ...
  visit(node.left);
  visit(node.right);
  node.print();          // post-order  : root cames last
  ...
}

As you can see we can say which print() comes first. With counting we cannot say if root is counted (+1) prior to subtrees or not.

This is question of convention.

Upvotes: 3

Sylvain Leroux
Sylvain Leroux

Reputation: 51990

We could say this is pre-order traversal as the count function is applied to a node before than to its children.

But the question is rather tricky as you are using direct recursion, doing both the traversal and the "action" in the same function.

Upvotes: 1

Related Questions