Iterative traversal in C - gives run time error


  • 0
    A

    I am attempting to implement the iterative solution for post order traversal, with one stack. The postorderTraversal() procedure below, gave expected results for sample trees I tried, but for a much complicated tree in OJ it threw run time error - The failed input was :

    [-64,12,18,-4,-53,null,76,null,-51,null,null,-93,3,null,-31,47,null,3,53,-81,33,4,null,-51,-44,-60,11,null,null,null,null,78,null,-35,-64,26,-81,-31,27,60,74,null,null,8,-38,47,12,-24,null,-59,-49,-11,-51,67,null,null,null,null,null,null,null,-67,null,-37,-19,10,-55,72,null,null,null,-70,17,-4,null,null,null,null,null,null,null,3,80,44,-88,-91,null,48,-90,-30,null,null,90,-34,37,null,null,73,-38,-31,-85,-31,-96,null,null,-18,67,34,72,null,-17,-77,null,56,-65,-88,-53,null,null,null,-33,86,null,81,-42,null,null,98,-40,70,-26,24,null,null,null,null,92,72,-27,null,null,null,null,null,null,-67,null,null,null,null,null,null,null,-54,-66,-36,null,-72,null,null,43,null,null,null,-92,-1,-98,null,null,null,null,null,null,null,39,-84,null,null,null,null,null,null,null,null,null,null,null,null,null,-93,null,null,null,98]

    I would really appreciate if someone could give me some tips on debugging this issue:

    1. How can the exact tree above be created as input to the program, to debug it locally - is the above a BreadthFirst node listing of the tree - or a PostOrderDepthFirst listng ?
    2. I tried to go through the execution of the procedure with pen and paper for upto a 6 level tree - I could not point out the the issue with the logic below - is there any major flaw in the logic that any of you can point out?

    Thanks a lot in advance, for your time and any tips you can provide. My apparently buggy code below :

    // post order iterative
    #define STACK_SZ 300
    #define MAX_RET_SZ 500
    typedef struct stack {
    	int size;
    	int top;
    	struct TreeNode** arr;
    };
    
    struct stack tree_stack;
    
    #define Init_Stack(stackArr, sz) tree_stack.arr = stackArr; tree_stack.size = sz; tree_stack.top = -1;
    #define Empty_Stack ((tree_stack.top == -1)? 1:0) 
    int Push_Stack(struct TreeNode* node) {
    	if(tree_stack.top == STACK_SZ-1)
    		return 0;
    	tree_stack.top++;
    	tree_stack.arr[tree_stack.top] = node;	
    	printf("push %d\n", node->val);
    }
    
    struct TreeNode* Pop_Stack() {
    	struct TreeNode* node;
    	if(tree_stack.top == -1)
    		return NULL;
    	node = tree_stack.arr[tree_stack.top];
    	tree_stack.top--;
    	printf("pop %d\n", node->val);
    	return node;
    }
    
    int* postorderTraversal(struct TreeNode* root, int* returnSize) {	
    	int *ret_arr = malloc(MAX_RET_SZ);
    	int  ret_arr_idx = 0;
    	struct TreeNode** stackArr = (struct TreeNode**)malloc(STACK_SZ*4);	
    	struct TreeNode *cur_node, *new_node;
    	Init_Stack(stackArr, STACK_SZ);    	
        cur_node = root;
    
    	while(cur_node) {
    		// if leaf then visit the node
    		if(cur_node->left == NULL && cur_node->right == NULL){
    			ret_arr[ret_arr_idx++] = cur_node->val;
    		}
    		// otherwise push the node and push its right child
    		else {
    			Push_Stack(cur_node);
    			if(cur_node->right != NULL) Push_Stack(cur_node->right);
    			cur_node = cur_node->left;
    			// repeat till we hit a leaf
    			if(cur_node) continue;
    		}
    		// we just visited a leaf, so pop one node from stack
                // which will be right child of the parent 
                // or if no right child present then the parent itself
    		while(!Empty_Stack) {
    			new_node=Pop_Stack();
    			//if cur node is, new node's left child and new node has no right child OR
    			//   cur node is new node's right child
    			// then visit new node
    			if((new_node->left == cur_node && new_node->right == NULL) || new_node->right == cur_node) {
    				ret_arr[ret_arr_idx++] = new_node->val;
    				// update cur node 
    				cur_node = new_node;
    			}
    			// otherwise break off the stack pop loop 
    			// and then push back the node 
    			else {
    				cur_node = new_node;
    				break;
    		}		
    	}
    	if(Empty_Stack) break;
    	}
    	*returnSize = ret_arr_idx;
    	free(stackArr);
    	return ret_arr;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.