3

Thinking of a parking lot it can be divided in to following hierarchy.

                                Structure

            Level1               Level2                 Level3

       Row1   Row2   Row3    Row1  Row2   Row3      Row1   Row2   Row3

       1...N   1...N  1...N  1...N N....N  1....N  1.....N 1....N 1.....N

Here bottom most level is 1 to N spots available in a row. It resembles very much like a tree data structure where each node can hold a value true if one of its subtree has a space available or false if all are occupied. And then next row or in case of a level, next level is examined. Now I have following questions:

  1. Is there a tree data structure which can have different number of child nodes at different level E.g it is 3 for level 2 and N for level 3.
  2. If such a tree is possible what will be its time complexity ?
  3. If such a tree is not possible what data structure can be used to represent this hierarchy.
Meena Chaudhary
  • 9,909
  • 16
  • 60
  • 94
  • you can do it by a simple tree only, the way you suggested, where finding place for a car and removing a car will take O(h) in worst case where h is the maximum depth of a node in the tree – advocateofnone Feb 16 '15 at 06:20
  • @sasha But how will I represent number of spots in each row which is different from number of rows at each level? – Meena Chaudhary Feb 16 '15 at 06:30
  • do you have only depth 3 hierarchy ( meaning L levels with each level R rows and with each row N slots) ? – Anudeep Gade Sep 08 '15 at 10:43

2 Answers2

0

Essentially, your question demands a tree that has arbitrary number of nodes at each level. Such a tree can be represented using the left-child, right-sibling representation. Instead of the usual left and right child pointers for the binary tree, in such a representation you have the following pointers.

  1. Left-child: This pointer points to the leftmost child of a node. Null if no child is present.
  2. Right sibling: This pointer points to the node immediately to the right of a given node (on the same level). Null if the given node is the rightmost node itself.

Above representation allows representing any arbitrary tree using O(n) space for n nodes. For details, see here.

Otherwise, you could also use a simple (C++) vector or a linked list to store the arbitrary number of child pointers at each node. Of course, this requires more memory than the left-child, right sibling representation, but at the same time, this is faster in terms of nodes processed when accessing a particular node.

Community
  • 1
  • 1
gjain
  • 4,468
  • 5
  • 39
  • 47
0

Answer to your questions:

  1. Yes, You can implement a tree based on your requirements. The Data structure would be something like this;

    public abstract class ParkingLotTreeNode {
    private ParkingLotTreeNode [] childNodes;

}

    This way, every Node will contain an array of its children nodes and this way you can have an arbitrary number of levels and rows for your parking lot.

  2. With the basic approach stated above, the worst case to find a parking lot will be the total numbers of parking spaces in the parking lot which is not a good solution for finding an empty slot.

    An improvement can be done to store a boolean flag which is set when the specific child has all its parking lot spaces are filled. At every node we'll have a flag representing if its child nodes have any free spots left.

    public abstract class ParkingLotTreeNode {
    private ParkingLotTreeNode [] childNodes;
    private Boolean isFull = false;
}

    This way finding the free slot will be done is in relatively a lot lesser time as we would know before hand which Levels/Rows are already full and will not be traversed.

Hope that helps!

ssadaqat
  • 158
  • 6