Tree traversal in Java -

Tree traversal in Java -

i studying job interview , reviewing trees, have no problem when traversing them got question haven't been able figure right reply to:

write function returns node in tree given 2 parameters: pointer root node , inorder traversal number of node want return. info stored in tree number of children each node.

so far, haven't been able figure why care of info stored in tree (the number of children). other if assume there's tree such:

5 4 7 3 1 4

then inorder traversal 341547but can't figure out code homecoming node want (for sake of argument i'm assuming inorder traversal number 2 - meaning want node of value 1).

i tried doing recursive traversal end screwing inner counter had tried different approach , tried set on stack can't figure how correctly so. far have:

public int findnode(root, position){ stack<integer> s = new stack<integer>(); cnode = root; //cnode = current node while(cnode.left != null) cnode = cnode.left; s.push(cnode); while(cnode.right != null) cnode = cnode.right; //stuck here. }

the recursive approach easier can't figure how check if have # i'm looking for:

public int findnode(root, position){ cnode = root; if(cnode != null){ findnode(cnode.left, position); system.out.print(cnode.data); findnode(cnode.right, position); } }

i know traverses tree still doesn't want. help appreciated.

you can such:

public node findnode(node root, int position) { arraylist<node> = new arraylist<node>(); populatenodes(root, a); homecoming a.get(position); } private void populatenodes(node node, arraylist<node> a) { if (node == null) return; populatenodes(node.left, a); a.add(node); populatenodes(node.right, a); }

note: don't need utilize data-structure if don't want, since had stack went it.

note2: jim garrison pointed out can optimize algorithm if have descendant count.

java binary-tree tree-traversal