A stack of index cards.
That answer probably sounds too glib to be entirely satisfactory, but it is an accurate description, especially for teams fortunate enough to be collocated.
Rather than locking down scope, projects using an agile approach set time as the fixed constraint through the use of a series of 2-4 week iterations. These iterations are organized into
a set of roughly quarterly releases (3-6 iterations in each release) that deliver functionality to the end users. One common way to determine the number of releases is based on the specific dates that functionality is needed. In some projects, cost may be the constraining factor, in which case the number of releases is determined by specific budget constraints. To establish the link between the number of releases and cost, a fixed team is typically assumed (and desirable).
However the number of iterations and releases is decided, project scope is represented as a "list of things to deliver" for the team. This list is described in a variety of ways, depending on what agile approach you are using. Scrum teams create a Product Backlog, which consists of a set of features or items, cleverly named Product Backlog Items. In Extreme Programming, the team develops a release plan consisting of a series of User Stories.
Whatever they're called, a subset of the entire list of Product Backlog Items or User Stories is identified for delivery during a given iteration, agreed to by the sponsor and the team, and then fixed so that -- from a delivery perspective -- the scope of that 2-4 week iteration cannot be changed. Once the things to be delivered within an iteration are determined, the team creates a set of tasks required to deliver the items/user stories.
This frequent subset planning is the main reason an agile WBS is (often literally) a stack of cards -- each card resembling a product backlog item/user story -- as opposed to a tree. On traditional projects, a fully fleshed out structure of deliverables, broken into tasks, is created at the beginning of the project. On an agile project, miniature lists are created every 2-4 weeks for the items being worked on directly. It's far easier to manipulate, alter, edit, and reprioritize a stack of index cards than an unwieldy tree diagram.
While the scope of a specific iteration on an agile project is fixed, the overall scope can fluctuate based on items being added to or removed from the Product Backlog. The Product Backlog may be organized into a release plan where specific items are targeted for delivery in a given iteration, but the actual content of each iteration is revised at each iteration planning meeting. This more fluid approach to scope allows the project team to better adapt to changing business conditions, deal more effectively with uncertainty, and employ more flexibility in their approach to solving problems than they can when a fully laid out Work Breakdown Structure is established at the beginning of the project.
There can be a downside, however. If agile teams are not careful, they may lose sight of the interrelationships between various items/user stories -- relationships that the traditional WBS hierarchy does an excellent job of portraying. One way of addressing this risk is to discuss key relationships between items/user stories during each iteration planning meeting, by explicitly asking, "What other items are related to this item that we are currently considering for inclusion in this iteration?"
For more about iterations and releases on agile projects, see our Technique Brief on Agile Planning. Our Technique Brief on Requirements Cards contains a detailed discussion of compiling product backlog items, user stories, or other agile WBS items, and our guidelines on Information Radiators and Standup Meetings describe common techniques for managing that stack of cards to completion.