Frage im Vorstellungsgespräch bei Meta
For a binary tree, write an iterator class, which can in-order traverse the binary tree, implement two operations, next() and hasnext(). E.g., if in-order traversing a binary tree will return 2 3 4 5 6, then first call next(), it will return 2, call next() again, it will return 3, etc.
Antwort im Vorstellungsgespräch
Anonym
i will solve the problem like this , i have Binary Tree class which implements iterator, so my Binary Trree will have implementation of three method next(),hasNext() and remove(). I also have method for InOrderTraversal -> for th purpose of this question i define an ArrayList and stored the data there as per InOrder Traversal public void inOrderIterator(Node X){ if(X.leftChild!=null){ inOrder(X.leftChild); //Next.add(X.leftChild); } //System.out.println(""+X.a); Next.add(X); if(X.rightChild!=null){ inOrder(X.rightChild); } } also override next() and hasNext() like this @Override public boolean hasNext() { if(!Next.isEmpty()) return true; else return false; } @Override public Node next() { // TODO Auto-generated method stub if(!Next.isEmpty()){ Node b=Next.get((Next.size() -1) -(Next.size()-2)); Next.remove((Next.size() -1) -(Next.size()-2)); return b; } else { return null; } } and then wrote a method to Print public void printIterator(){ while(hasNext()){ System.out.println(""+next()); } }